第2節
ユークリッドの互除法 133
ax+ by=c の整数解
B
次の方程式の整数解をすべて求めよ。
例題
8
31x+22y=3
解答
31x+22y=3
*=5, y=ー7 は, 31x+22y=1 の整数解の1つである。
の
よって
31·5+22-(-7) =1
両辺に3を掛けると
31·15+22-(-21) = 3
0-2 から
31(x-15)+22(y+21) = 0
31 と 22 は互いに素であるから, ③より
3
10
x-15= 22k, y+21= -31k(kは整数)
したがって,①のすべての整数解は
x= 22k+15, y=-31k-21(kは整数)
補足> 31 と 22 は互いに素であるから,31x+22y=3 を満たす整数x, yは必ず
存在するが,実際にそれらの整数を見つけるのは簡単ではない。このよ
15
うな場合,まず, 31x+22y=1 の整数解を1つ見つけるとよい。
このとき,互除法が利用できる。31 と 22 に互除法を用いると
31 = 22·1+9
移項すると 9=31-22·1
22 = 9·2+4
移項すると 4= 22-9·2
20
9=4·2+1
移項すると 1=9-4·2
よって
1=9-4-2=9ー(22-9·2).2
=9:5+22·(-2)
= (31-22-1)-5+22-(-2)
= 31-5+22-(-7)
やめと
I「間