重要 例題29 ユークリッドの互除法と1次不定方程式
(1) 不定方程式 161x+19y=1を満たす整数x,yの組の中で, xの絶対値が最|
①小のものはx=アイ,y=ウエである。
(2) 不定方程式 161x+19y=5 を満たす整数x,yの組の中で, xの絶対値が最
a
大量
小のものはx=オ,y=カキクである。
POINT !
1次不定方程式の整数解の1組が容易に見つからない場合は,
ユークリッドの互除法を用いる。 (
51 参考)
(2) (1) の等式の両辺を5倍すると 161(5x) +19(5y)=5
よって,(1) で見つけた整数解の1組をそれぞれ5倍したものは
161x+19y=5の整数解の1組である。
解答 (1) 161x+19y=1
161=19.8+9
19=9・2+1
この計算を逆にたどると
1=19-9・2
01-
=19-(161-19・8)・2
=161・(-2)+ 19・17
① とする。
移項すると 9161-19・8
移項すると 119-9・2
......
(2-8-) (ar-
したがって
161・(-2)+19・17=1
① ② から 161(x+2)+19(y-17) = 0
161 と 19 は互いに素であるから、③より
......
(2) 161x+19y=5
②から
④ - ⑤ から 161(x+10)+19(y-85)=0
161 19 は互いに素であるから, ⑥ より
..... (2)
x+2=19k, y-17-161k (kは整数)
よって
x=19k-2, y=-161k+17
|x|が最小となるのはん=0のときであるから
x=アイ- 2,y=ウェ17
④ とする。
161・(-2.5)+19.(17･5)=5 ...... ⑤
⑥
1s)(3)
③
xの係数 161 とyの係数
19 にユークリッドの互除
法の計算を行う。
6518-5
x+10=19l, y-85-1617 (Zは整数)
よって
x=191-10, y=-161+85
|x|が最小となるのはl=1のときであるから
x=オ9, y=カキクー76
◆余りが1になったところ
で,計算を逆にたどる。
0
← ① を満たす 1組の解
01-x=-2,y=17 が得られる。
al-
a
I
& meroun
SHOR
H.260
•②×5 とすると, ④ を満た
す1組の解x=-10,
|y=85 が得られる。
