Think
256 方程式の整数解(3)
[ 不定方程式 57x+13y=1 の整数解を求めよ.
(方
解答
例題255のように特殊解を求めたいが,
係数が大きいため実際に値を代入して求めるのは困難である。
57×(整数)+13×(整数)=1
の式をつくるために, ユークリッドの互除法を用いる.
方程式 57x+13y=1 ...... ① の係数 57と13について
ユークリッドの互除法を用いる.
57=13×4+5 より
57-13×4=5
13=5×2+3 より
13-5×2=3
......3
5=3×1+2 より
5-3×1=2
・④
3=2×1+1 より
3-2×1=1
......
⑤
3 不定方程式 515
****
Ocus
⑤④を代入して,
3-(5-3×1)×1=1
3×2-5×1=1
これに③を代入して,
(13-5×2)×2-5×1=1
13×2-5×5=1
5-3×1
3-②×1=1
AA(S)S S-V
13-5×2
(x)+
③ ×2-5×1=0
13×2-(57-13×4)×5=1
これに②を代入して,
したがって,
① - ⑥より
57×(-5)+13×22=1.... ⑥ x=-5,y=22が
57(x+5)+13(y-22)=0
57(x+5)=13(22-y) ...⑦
57と13は互いに素であるから,x+5は13の倍数となる.
したがって, んを整数として
x+5=13k
すなわち, x=13k-5 (S2)
これを⑦に代入すると,
57k=22-y より, y=-57k+22
よって、 求める一般解は,
①の解の1つ
とする
57×13k=13(22-y)
Date
- Jez
与えられた方程式の係数が大きい場合は,係数について
33
x=13k-5,y=-57k+22 (kは整数)
ユークリッドの互除法を利用して考える
第9