53
例題
124
不定方程式の整数解とユークリッドの互除法
不定方程式7x-17y=4 の整数解をすべて求めよ。
考え方 ユークリッドの互除法を利用して, 7x-17y=1の整数解を1組求め、
8881 Saps
辺を4倍する。
7x-17y=4......①
7と17は互いに素であるから, 7x-17y=1を満たす整数x,yが存在する。
7と17について,ユークリッドの互除法を利用すると,
17=7×2+3
...2
10%
7=3×2+1
この計算を逆からたどっていくと,
③より,
EDE
7-3×2=1 ......④
②より
3=17-7×2
これを ④ に代入すると,
-7-(17-7×2)×2=1
よって,
RAHSON ac
TAS
ESE
を利用する 18E
TEE
Ee
x-20=17k, すなわち, x=17k+20
⑦ に代入して, 7×17k=17(y-8) より,
-3h
7×5-17×2=1.......
が成り立ち, x=5, y=2は7x-17y=1の整数解の1組である。
⑤ の両辺に4を掛けると,
7×20-17×8=4...... ⑥
① - ⑥より,
7(x-20)-17(y-8)=0
7(x-20)=17(y-8) ......⑦
7 と 17 は互いに素であるから,⑦よりkを整数として,
8=(1+x)2 (£)
(E)
y=7k+8
よって, x=17k+20, y=7k+8 (kは整数)
KOLI