【第3章】
(4)べズーの定理
a,bが互いに素のとき、
ax+by=1を満たす整数(p,q)が存在する。
(例)37x+27y=4を満たす整数(x,y)を求めよ。
(解)
a=37, b=27とする。
37=27+10より、10=37-27=a-b
27=10×2+7より、
7=27-10×2=b-2(a-b)=-2a+3b
10=7+3より、
3=10-7=(a-b)-(-2a+3b)=3a-4b
7=3×2+1より、
1=7-3×2=(-2a+3b)-2(3a-4b)=-8a+11b
辺々に4を掛けて、
4=-32a+44b
37×(-32)+27×44=4
特殊解(x,y)=(-32,44)を得る。
一般解(x,y)=(27t-32, -37t+44)
べズーの定理で、ax+by=1の特殊解(p,q)を求めることができれば、
ax+by=kの特殊解(kp,kq)が得られる。
上の例では、t=1とすると、
(-5, 7)も特殊解である。
37×(-5)+27×7=4
途中の計算を使って、
10=a-b, 7=-2a+3bより、
4=7×2-10=2(-2a+3b)-(a-b)=-5a+7b
すなわち、37×(-5)+27×7=4
特殊解(x,y)=(-5,7)
一般解(x,y)=(27t-5, -37t+7)
