Question

なたろー

数学Aのユークリッドの互除法です！この問題をユークリッドの互除法を使ってこのように解くことができるらしいのですが、ユークリッドの互除法は最大公約数を求める方法なのに、なぜ使うことができるのですか？

144 第3章 整数の性質
31 と 22 に互除法の計算を行うと,次のようになる。
移項すると 9=31-22·1
31=22·1+9
移項すると 4=22-9-2
22=9·2+4
移項すると 1=9-4·2
9=4-2+1
5
よって
1=9-4-2
4に22-9·2 を代入
=9-(22-9·2)·2
9に 31-22·1を
代入
=9·5+22·(-2)
=(31-22-1)-5+22·(-2)
=31-5+22-(-7)
10
すなわち
31·5+22-(-7)=1
の
よって,求める整数 x, y の組の1つは x35, y=-7
(2) 等式31x+22y=3 を満たす整数 x,yの組を1つ求める。
のの両辺に3を掛けると 31·(3·5)+22·{3·(-7)}=3
15
すなわち
31·15+22-(-21)=3
よって,求める整数 x, yの組の1つは
x=15, y=-21 終

数学a ユークリッドの互除法