裴蜀定理详解
最编程
2024-07-18 22:31:09
...
如果 a 和 b 有一个是0，那么它们两个的最大公约数是0。这时定理显然成立。
以下证明a和b都不等于0的情况。不妨设a,b都大于零，a>=b.设(a,b)=d
对ax+by=d，两边同时除以d，可得(a1)x+(b1)y=1，其中(a1,b1)=1。
转证(a1)x+(b1)y=1。由带余除法：
a1=(q1)b+(r1),其中0=<r1<b1
b1=(q2)(r1)+(r2),其中0=<r2<r1
(r1)=(q3)(r2)+(r3),其中0=<r3<r2
.....
(rn-3)=(qn-1)(rn-2)+(rn-1)
(rn-2)=(qn)(rn-1)+(rn)
(rn-1)=(qn+1)(rn)
于是，有(a1,b1)=(b1,r1)=(r1,r2)=...=(rn-1,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=(a1)x+(b1)y。
以下证明a和b都不等于0的情况。不妨设a,b都大于零，a>=b.设(a,b)=d
对ax+by=d，两边同时除以d，可得(a1)x+(b1)y=1，其中(a1,b1)=1。
转证(a1)x+(b1)y=1。由带余除法：
a1=(q1)b+(r1),其中0=<r1<b1
b1=(q2)(r1)+(r2),其中0=<r2<r1
(r1)=(q3)(r2)+(r3),其中0=<r3<r2
.....
(rn-3)=(qn-1)(rn-2)+(rn-1)
(rn-2)=(qn)(rn-1)+(rn)
(rn-1)=(qn+1)(rn)
于是，有(a1,b1)=(b1,r1)=(r1,r2)=...=(rn-1,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=(a1)x+(b1)y。
上一篇： ACM 数论裴枢定理（贝祖定理）
下一篇： 裴蜀定理