移項すると
16 = 154
154 = 69·2+16
移項すると
5= 69
69=16·4+5
移項すると
1= 16
16 =5·3+1
5=1·5+0
割り算の等式a=bq+r にお
余りrをa, bの式で表す。
①, ②, ③ の計算を逆にたどると
1= 16-5·3
介③1を16
=16-(69-16*4)·3
② より 5
69, 16 に
16·13+69·(+3
= (154-69-2)·13+69·(-3)
合のより
ニ
154, 69
= 154·13+69·(-29)
ニ
よって
154·13+69·(-29) =1
このように,互除法の計算を利用すると, 2つ
数gを,適当な整数p, qを用いて ap+bq=g
kくて
が互い 圭でもるとき
an+