(2)等
CHART
D GUIDE
a,
等式 ax+by=1 (a, 6は互いに素) を満たす整数x, y
互除法の計算を利用
bが互いに素のときは, ax+by=1 を満たす整数x, yが必ず存在する。
互除法の計算を, 余りが1になるまで行う。
2の計算を, (1) の解答のように逆にたどって,
131と17を使って表すように式変形する。
(2)31+17=1 ならば、両辺を4倍すると
←31と17は互いに素
31・4 + 17・4=4
よって、 (1) で求めたx,yの組に対して 4x, 4y が求める組の1つである。
解答
(1)31=17・1+14
移すると
17=14・1+3
移すると
14=31-17・1
3=17-14・1
①
14=3.4+2
移すると
②=14-3・4
2|22|0
132-1
4
1
1 2 3 14
17 ) 31
2 12 14
2
17
3 14
3=2・1+1
移すると
1=3-2・1
4
よって
1=3-2・1
-3-(14-3-4).1
=35+14・(-1)
=(17-14・1)・5+14・(-1)
=17・5+ (31-17・1)・(-6)
=17.5+14(-6)
=31・(-6)+17・11
■④の2に③を代入。
■ 3, 14 について整理。
◆3に②を代入。
◆ 17, 14 について整理。
14に①を代入。
◆ 31, 17 について整理。
したがって, 31 (-6)+17・11=1 が成り立つから,求める 186+187=1
整数x, yの組の1つは
x=-6, y=11
(2)(1) から, 31(-6)+17・11=1 が成り立つ。
この両辺を4倍して 31. (-24)+17・44=4
よって, 求める整数x, yの組の1つは
x=-24,y=44
■-744+748=4