表題
互除法を利用して,次の等式を満たす整数x,yの組を1つ求めよ。
(1) 24x+19y=1
(2) 63x+44y=2
(3) 95x-28y=1
(4) 141x-52y=4
解説
(1) 24 19 に互除法の計算を行うと,次のようになる。
24=19・1+5
移項すると 5=24-19・1
19=53+4
移項すると 4=19-5・3
5=4・1+1
移項すると 1=5-4・1
よって
1=5-4・1=5-(19-5・3)・1
=5・4+19・(-1)
=(24-19.1)・4+ 19· (−1)
=24.4 +19・(-5)
すなわち
24.4 +19・(−5)=1
よって, 求める整数x,yの組の1つは x=4, y=-5
参考 割り算の等式を利用して係数を小さくする方法を考えてみる。
24=19・1+5より, 方程式は次のようになる。
( 19.1 +5)x + 19y=1
整理すると 5x+19(x+y)=1
19=53+4 より 5x+(5•3+4)x+y)=1
すなわち
5(4x+3y) + 4(x+y)=1
4x+3y=m, x+y=n とおくと 5m+4n=1
この等式を満たす整数 m, n の組の1つは m=1,n=-1
4x+3y=1, x+y=-1 を解くと x=4, y=-5