例9
ax+by=c を満たす整数 (互除法の活用)
等式 ax+by=c を満たす整数x,yの組を求めてみよう。
言 (1) 等式 177x+52y=1を満たす整数x,yの組を1つ求める。
177と52 に互除法の計算を行うと,次のようになる。
177=52・3+21
移項すると 21=177-52・3
52=21・2+10
移項すると
10=52-21・2
21=10・2+1 移すると
1=21-10・2
3 Me
③②, ① の式から
1=21-10・2
=21-(52-21・2)・2
=21.5+52(-2)
1012
10 に ② の右辺を代入
J21 13
.....
.....
5o
......
21 に ① の右辺を代入
①
(2)
(③3)
=(177-52・3)・5+52(-2)
すなわち
177.5+52(-17)=1
4
よって, 求める整数x,yの組の1つはx=5,y=-17
(2)等式177x+52y=3 を満たす整数x,yの組を1つ求める。
④の両辺に3を掛けると 177・3・5)+52・3・(-17)}=3
すなわち 177・15+52・(−51)=3
よって, 求める整数x,yの組の1つはx=15, y = -51 終