数学
高校生
解決済み

ユークリッドの互除法の問題です。
互除法をしていくときに、学校では「1が出たら終わり」と習ったのですが、この問題では注意があるらしく、「右辺10の約数5が余りとして出てきているため」などど書いてありますが、いまいち書いてあることが理解できません。
それが問題を解いていく際に影響があるのでしょうか?余りが1になるまでやっては行けない理由はなんでしょうか?
教えてください🙏

(4) 103x-38y=10
よって、 7a-176=1 より 90.7+37 · ( 17 ) = 1 両辺に2を掛けて 90-14+37-(-34)=2 よって、 求める整数x、yの組の1つは x=14,y=-34 解答編 243 =(103-38-2)-3+38-(-2) =103.3+38(-8) 数学A 問題・演習問題 移項すると 1662-23-2 すなわち =103-3-38-8 103-3-38-8=5 よって, 求める整数x、yの組の1つは x=6, y=16 (3)6223に互除法の計算を行うと,次のように 両辺に2を掛けて 103-6-38-16=10 なる。 62=23・2+16 23=16.1+7 16-7-2+2 移すると 移すると 移項すると 7=23-16-1 2=16-7-2 1=7-2-3 よって 1=7-2.3 7=2・3+1 =7-(16-7-2)-3 =7-7+16-(-3) =(23-16-1)-7+16-(-3) =23-7+16-(-10) =23-7+(62-23-2)-(-10) =62(-10)+23-27 =62 (-10)-23-(-27) すなわち 62 (-10)-23-(-27)=1 両辺に5を掛けて 62-(-50)-23-(-135)=5 よって, 求める整数x、yの組の1つは x=-50,y=-135 注意①の時点で等式の右辺10の約数 5が余りと して出てきたため,そこで互除法の計算を止め ている。 別解 a = 103, 6=38 とおく。 10338の互除法の計算から 27=103-38-2 より 11=38-27-1 より 5=27-11-2より 27=a-b2=α-26 11-b-(a-2b)-1 =-a+3b 5=(a-2b)-(-a+3b)-2 =3a-8b よって, 34-86=5 より 103.3-38.8=5 両辺に2を掛けて 103.6-38.16=10 よって、 求める整数x、yの組の1つは x=6, y=16 別解 a=62, 6=23 とおく。 6223の互除法の計算から 16=62-23.2より 723-16-1より 16=a-b2=α-26 7=b-(a-2b)-1 2=(a-2b)-(-a+3b)-2 = -a+36 2=167.2より =3a-8b 1=7-2・3より 1=(-a+3b)-(3a-8b)-3 =-10a+276 よって, -10α+276=1より 62(-10)-23·(27)=1 両辺に5を掛けて 62 (-50)-23-(-135)=5 よって, 求める整数x、yの組の1つは x=-50,y=135 (4)103 38 に互除法の計算を行うと,次のよう になる。 103=38・2+27 移項すると 27=103-38-2 移項すると 11=38-27-1 移すると 5=27-11-2 38=27.1+11 27=11.2+5 よって 5=27-11-2 5)-3 =27-38-27-1)-2 448 32351 23009-1+9342 230099342-2+4325 9342-4325-2+692 4325=692.6+ 173 692=173-4+ 0 よって, 最大公約数は 173 参考 449 4 6 2 2 1 173) 692 692 4325 9342 23009 32351 4152 8650 18684 23009 20 173 692 4325 9342 [指針] 2数の最大公約数が1であることを示せばよい。 まず2つの式の関係をa=bg+rの形に表す。 (1) n+1=1+1 よって, n+1とnの最大公約数は, nと1の最 大公約数であるからである。 したがって, n と n+1は互いに素である。 (2) n2+n+1=(n+1) ・ n+1 ① よって, n2+n+1 と n+1の最大公約数は, n+1と1の最大公約数であるからである。 したがって, n2+n+1とn+1は互いに素であ る。 =27-3+38(-2)
ユーグリッドの互除法

回答

✨ ベストアンサー ✨

1までやってはいけないのではなく
1までやるより楽なとこで止めることができる
と言っています

背水の陣

なるほど!
つまり1までやっても少し手間がかかるだけで答えは同じになるということでしょうか??

答の見た目は変わり得ますが、
本質的には同じになります

この回答にコメントする
疑問は解決しましたか?