Question

背水の陣

ユークリッドの互除法の問題です。
互除法をしていくときに、学校では「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)

ユーグリッドの互除法

Answer 1

✨ คำตอบที่ดีที่สุด ✨

和

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

背水の陣

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

和

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