-
130 第7章 整数の性質
重要 例題 29 ユークリッドの互除法と1次不定方程式
(1) 不定方程式 161x+19y=1を満たす整数x,yの組の中で, xの絶対値が
小のものはx=[アイ, y=ウエである。(一
(2) 不定方程式 161x+19y=5 を満たす整数x,yの組の中で,xの絶対値が最
小のものは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
①とする。
移項すると 9161-19.8
移項すると1=19-9・2
......
(01-) (ĉ— 8-) (ar
=19-(161-198) ・2
=161(-2)+19・17_
したがって
161・(-2)+19・17=1
① ② から 161(x+2)+19(y-17)=0
161 19 は互いに素であるから、③より
(2)
x+2=19k, y-17-161k(kは整数)
よって
x=19k-2, y=-161k+17
|x|が最小となるのはん=0のときであるから
x=アイー 2,y=ウェ17
(2) 161x+19y=5
④とする。
②から
161・(−2・5)+19・(17・5)=5
④ ⑤ から 161(x+10)+19(y-85)=0
161 19 は互いに素であるから,⑥より
(5)
x+10=19l, y-85-161Z(Zは整数)
よって
x=19-10, y=-161+85
|x|が最小となるのはl=1のときであるから
x=オ9, y=カキクー76
201
0
←xの係数 161 とyの係数
19 にユークリッドの互除
法の計算を行う。
余りが1になったところ
で, 計算を逆にたどる。
← ① を満たす 1組の解
x=-2, y=17 が得られる。
②×5 とすると④を満た
す1組の解x=-10,
y = 85 が得られる。
参考 x,yの係数の値が大きいときは,係数を小さくする方法が