为什么只要a、b互素,就必然存在整数x、y,使得ax+by=1

Question

为什么只要a、b互素,就必然存在整数x、y,使得ax+by=1

Answer 1

不妨设a,b都大于零,a>=b,用带余除法：
a=(x1)b+(r1),其中0=b=(x2)(r1)+(r2),其中0=(r1)=(x3)(r2)+(r3),其中0=.到第n步,会有（这是因为数列rn单调递减到0）
(rn-3)=(xn-1)(rn-2)+(rn-1)
(rn-2)=(xn)(rn-1)+(rn)
(rn-1)=（xn+1)(rn)+0
容易证明a和b的最大公因数=b和r1的最大公因数=r1和r1的最大公因数=.=(rn)和0的最大公因数,所以（rn）=1,所以倒数第两个式子是
(rn-2)=(xn)(rn-1)+1
即1=(rn-2)-(xn)(rn-1)
由倒数第三个式子（rn-1）=(rn-3)-(xn-1)(rn-2)代入上式,得
1=[1+(xn)(xn-1)](rn-2)-(xn)(rn-3)
然后用同样的办法用它上面的等式逐个地消去(rn-2),...(r1),
得到1=ax+by.
这个是理论上求a,b的方法.