15
10
154
5
例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
②① の式から
1=21-10・2
10 に ② の右辺を代入
......
=21-52-21・2)・2
=21・5+52・(−2)
=(177-52・3)・5+52・(-2)
すなわち
177・5+52・(-17)=1
HORA
よって 求める整数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 終
練習 次の等式を満たす整数xvの組を1
21 に ① の右辺を代入
177 と 52 の最大公約数は1である。すなわち, 177 と 52 は互いに素
0 であるから,177x+52y=1を満たす整数x,yの組は存在する。 しかし,
その整数は簡単には見つけることができない。
例9のように互除法の計算を利用すると、互いに素である2つの整数
a,b に対して, ax+by=1を満たす整数x,yの組を必ず見つけるこ
とができる。
5
方
10