(1) 方程式 63x+29y=1 ・・・・・・ 1① の係数 63 と 29 につ
いてユークリッドの互除法を用いる.
63=29×2+5 より
29=5×5+4 より
5=4×1+1 より,
④に③を代入して
これに②を代入して、
63-29×2=5 ......
②
29-5×5=4...... ③
3
5-29-5×5)×1=1
5-4×1=1 ......④
(4)
(63-29×2)×6-29×1=1
5×6-29×1=1 $1=4+)
63×6+29× (−13)=1
(2) 73x-26y
したがって,
①-⑤ より, 63(x-6)+29(y+13)=0
なる.
したがって, んを整数として
6-x=29k, すなわち,
63(6-x)=29(y+13) ...... ⑥
63と29は互いに素であるから, 6-xは29の倍数と
・⑤
x=-29k+6
63×29k=29(y+13)
これを⑥に代入すると,
63k=y+13 より,
よって、求める整数解は,
x=-29k+6,y=63k-13 (nは整数)
y=63k-13
1202
の係数 73と26 につ