inupri web fc2.com) 赤阪 正 純 (httpソ フ ユ ーク リッ ドの互除法 共通 の素因数 pが 存在す るので,ι ― αご は ,で 割 ① +9y=(3″ +7y)× 1+(″ 3″ +7y=(″ +2υ )× 3+υ 4″ +2υ ) ので,α と 0も 互 いに素 ではない よって対偶命題 が証明 されたので ,元 の命題 は正 したがって,ユ ー クリッドの互除法より,4″ +9υ の最大公約数は,υ と″の最大公約数 実く [』tyυ ｀ ｀ し 夕 ″とυは互いに素なので,4″ +9υ と3″ +7υ も い に わ ち は る 素な あ 帥数で 寺境卜 り互 ,す ■ ( ″注 (4″ , )で +9υ ,3″ 表記 すれ ば +7y)=(3″ +7υ ,″ +2υ ) =(″ +2υ ,υ ) =(υ ,″ ) とな ります しい (2)編 で あ り,さ らに とな る ② より,7″ +1と 1は 互いに素だから,(1)よ +4と 7π +1も 互 い に素 で あ る よつて ,① よ り,21π +4と 771+1は 互 い に素 だか ら,(1)よ り,21π +4と 28π +5も 互 い に素 り,21π であ る も しれ ませ ん 4 . 21π 自然数 亀 は に と 28π とみも互いに素 であることを証明 せよ '=,+dの (2)任 意 の 自然数 πに対 し,28π +5と 21π +5=(21″ +4)× 1+7π +1 +4=(7π +1)× 3+1 したがって,ユ ー クリッ ドの互 除法 より,21π マヽ しも 関係 があるとき ,α と οが互 いに素 な らば,α +5の 最大公約数 は,7π +1と +4 1の 最大公 約数 に等 しい +4 7π は互いに素 であることを証明せ よ つヽ し その場合 は次 の よ うな解答 にな るで しょう 28π 伊 ② 鰤 代 )の 問題 です '} , =デ 鴇 +3… 需 ① 珍 注 今 の時 代 な ら (2)が い きな り出題 され るか とてもシンプルで見やす いですね (つ ま リユー ク リッ ドの互 除法な ど習 っていない時 こた =:給乳 +1… ■ 次 の問題 は,整 数問題が教育課程 になかった時代 例 題 よって,0も っ で割 り切れる ことになる り切れる =υ × 2+″ ″+2υ ① (3) +1と 1は 互 い に素 なので ,21多 +4と 28π +5 も互 い に素 であ る [2000年 大阪市大前期理系] ■ 考え方 今 の時代な ら,(1)は ユー クリッ ドの互 除法 よ り明 らかです なぜ な ら,3=:+α =α グ+ε で,こ れは,う を αで割 った ら商 が ご,余 りが 0で あることを意味 してお り,ユ ーク り,う リッドの互除法によ り,う とαの最大公約数 は αと 0の 最大公約数 に等 しいので ,α と 0が 互 いに素な らば,α と うも互いに素 だか らです ″注 よ ( , )で 表記 すれ ば (28π +5,21π +4)=(21η +4,7η +1)=(7π +1, 1) とな ります。 とてもシンプルで見やす いですね 次 の問題 は,某 予備校 の模擬試験 の問題 です 校 の生徒も出来がかな り悪か った問題 です しか し 「ユー クリッドの互 除法 より明 らか」 と解答す るわけにも 例題 5 ″,υ の 方程 式 7″ (2)は ,(1)の 結果 を利用 しますが,こ の問題 も (1)(*)を 満 たす整 数 の組 ユー ク リッ ドの互除法 の意識 があると解決が早 いで めよ すね (2)(*)を 満 たす整 数 の組 (1)を =,十 ―αグ =ο α より, ι― -4y=6 (*) がある いかないので きちん と証明 しましよう 0 本 . αと ιが互いに素 でない と仮定す ると,α とらに (″ ,y)を 1つ 求 (″ ,υ )を すべて 求め よ ￨(3)(*)を 満 たす 自然数 の組 (″ ,υ )を 考 え イ´燎 t ｀ー イく ヽ7■ 赤阪 正 純 (htt● グ nupri.web.fc2.com) る ,と ユ ー ク リッ ドの互 除法 υが互いに素 となる組 の うち,″ の値 が小 さいほ うか ら 100番 目の組 (″ ,υ )を 求 めよ )=(2+4た ,2+7カ )に おいて (i)た =6カ ,6々 +2,6カ +4の とき (″ ,υ K塾 第 2回 全統記述模試 ] ない =6た +1の とき (ii)た (1)(2)は 問題 ない と思 い ます 考え方 (3)が 全然お手上げだったようで残念でな りません 「100 番 目を求 め よ」なんて聞かれるとい うことは絶対 に 何らから もずです 少なくともイロイ J世 がある 、員 ロ こ と くらい はで きて ほ し 予想 で きれ ばあ とは証 明 で す 0 (1)(″ +1)=24た +6=3(8々 +2) υ=2+7(6た +1)=42々 +9=3(14た +3) ″ =2+4(6λ よって,″ も υ も共に 3の 倍数 になるので互いに 素 にはな らない . +3)=24た +14 υ=2+7(6λ +3)=42た +23 1組 の 解 な (υ ので ６ ６ 一 一〓 υ ２ ４ × × ４ 一 一 ″ つん × × ウ ′ワ ′ +9) =(18た +9,6た +5) ゛ず 確 協寸３ -2)-4(υ -2)=0 -2)=4(υ -2) 7と 4は 互 い に 素 な の で ,″ → .illく -2が 4で 割 り切 -2=4た とお け ,従 って υ-2=7た ヽ「 雅 主lF 慾 七 島J、 ″ と υ の最大公約数 は,6た D -1と 6の 公約数 に等 しいが,6カ ー 1は 6で 割 り切れな いので,6カ ー 1と とな る 以上 よ り,7″ (″ -4υ 6の 公約数 は 1,つ ま り,″ と yは 互 いに素 である =6の 一般 解 は . ,y)=(2+4た ,2+7た )(た ， ， ６ ︱︱︱︱︱← ０乙 〓υ ︱ノ Ｏ乙 １ ■ ヽ ６ ”略け ｍ ≫ ， ０ ３ ワ１ ９ ４ αυ ００ ０乙 ・ Ｉ工 ， ， ３ ２ ８ ︲ 掛孵辮”︻ ６ １ ４ １ ′仕 ０６ １■ αυ ′υ ９ ０ １ ２ ２ ７ ３ ６ ２ ４ ４ ０ ３ ︲ ５ ４ ３ ８ ５ ８ ３ ５ ６ ２ ４ ２ ７ ６ ４ ９ ７ ,卜 が ″ と の 只り もし υ 最大公約数 は,6カ +1と 6の 公約数 に等 ヽ ヽ を ヽ しいが,6た +1は 6で 割 り切れないので,6た +1と し、セ臭: 6の 公約数は 1,つ まり,″ と υ は互いに素 で ある ω ０ ５ ６ ８ ４ ５ ３ ９ じ∼ ) この結果から,た が 6で 割って余 りが 3ま たは5の ときに ″ と型 が互いに素 になってい ることがわか この予想 が正 しい ことを証明する 一 一 一 一 一 一 一 一 〓 ６ ０■ ２ ３ １ ２３ ４５ ６ ７ ８ ９ １ １︲ × × × ○ × ○ × × × ○ × ○ × × 互いに素 か どうか ″ りた に順 番 に整数 を代 入 してみ る と υ (3)(2)よ +5の とき ″ =2+4(6λ +5)=24た +22 υ=2+7(6λ +5)=42々 +37 (iv)た =6た は整 数 ) とな る る ｀ ‐ド0 ‐ つり ]:￨￨:∬ 1,1::1:; 1.2‐ れる つ ま り,″ ,″ )=(42た +23,24た +14) =(24た +14,18々 辺 々 を 引 いて ,7(″ 7(″ =6々 +3の とき (iii)々 ″ =2+4(6た ,υ )=(2,2) り (″ ,υ )=(2,2)が (2)(1)よ ͡ , ″ も υ も共 に偶数 になるので互 いに素 にはな ら [2015年 いで す (4) 以上 よ り,た が 6で 割 って余 りが 3ま たは 5の と きに ″ と υが互いに素 である したがって,100番 目の組 は たが 6で 割 って 5余 る数の 50番 目に相当す るので , た=5+6(50-1)=299 この とき,(″ ,υ )=(1198,2095) ｀う ,ド い 「]― ク リ 静払」,7.キ 環穴状 "激 1ミ ｀ ヽネ マヽ z牛 め37■ 1じ ゃ ・ υ 彙ぶ テ アヽ ィ
© Copyright 2024 ExpyDoc
