不定方程式と互除法
の計算を逆にたどると,1次不定方程式の整数解の1つを見つ
ことができる。
レえば、 26x+11y=1 の係数 26 と 11 に互除法を適用すると,次
こうになる。
26=11·2+4
一変形すると 43D26-11·2
11=4·2+3
そ変形すると 3=11-4·2
4=3·1+1
←変形すると134-3·1
3=1-3
- 26 と11の最大公約数は
余りに着目して,この計算を逆にたどると
1=4-3-1=4-(11-4·2)-1、
=4·3-11·1=(26-11·2)-3-11·1
=26-3-11-7
よって
26-3+11·(-7)=1
したがって, 26x+1ly=1 の整数解の1つとして x=3, y=-7 た
暮られる。
互いに素な2つの整数に互除法を適用すると,余りが0になる直前C
り算の余りは必ず1になる。そして、上のように互除法の計算を逆じ
こどることができるので、 次のことが成り立つ。