贝祖定理及其证明

大家好，欢迎来到IT知识分享网。

一、贝祖定理的两种写法

写法一

若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

写法二

两个整数 a、b 是互质的，等价于方程 ax+by=1有整数解。

联系

在写法一中，存在 x、y使得A * x + B * y = d 成立，此时对两边同时除以 d ，将得到：

a * x + b * y = 1

说明了这两种写法是等价的。

二、贝祖定理的一种证明

参考写法二证明贝祖定理

1.准备工作

两个整数 a、b 是互质的，等价于方程 ax+by=1有整数解。

通过对x，y的不同取值，方程 ax+by将取不同的值。

若在x = X，y = Y时，aX+bY取值为 S ，且 S 为a、b线性组合可以得到的最小的正整数。

2.证明S为a，b的公约数

将a对s进行取模：a = q * S + r （0<=r<S）;

此时 有a * X + b * Y = S；

将两式联立，可解得：

r = a – q * S = a – q * （a * X + b * Y ）=a – a * q * X – b * q * Y

= a*（1-q * X）+ b* （ – q * Y）；

已知 0<=r<S，又因为S 为a、b线性组合可以得到的最小的正整数，
所以 r 只会为0

即 S 是 a 的一个约数。

同理可以用来证明 S 也是 b 的一个约数.

又因为a、b为互质关系，所以 S 为 1；

三.贝祖定理扩展

1.内容：

方程a * x + b * y = n有解的充要条件为 n 是 gcd （a，b）的倍数。

2.两个引理

1.If a,b and c are integers such that a | bc and gcd (a, b) = 1gcd(a,b)=1, then a |c.

若a 可以整除 b * c ，那么 a 其实是b* c的一个约数，当a，b互质时，a仅可能是 c 的约数。

2.If a,b and c are integers such that a | c, b | c and gcd (a, b) = 1, then ab | c.