贝祖定理定义

（a,b）代表最大公因数，则设a,b是不全为零的整数，则存在整数x,y，使得ax+by=（a，b）

证明

记d=（a,b），u(k)，k为角标，则由欧几里得算法得，u0 =a，u1=b（这里不妨设b≠0），则由整除的性质，可知d | u(2),d | u(3)……，d | u (k+1)，所以d≤u（k+1）

反过来，再由整除的性质，可由u（k+1） |u（k），u（k+1） | u（k-1），......，u（k+1） | u（1），u（k+1） | u(0),即u（k+1）为a与b的一个公因数，因此，u（k+1）≤d

上述讨论表明：d=u（k+1），现在倒过来利用欧几里得算法中的式子，可知

u（k+1）=u（k-1）-u（k）q（k-1）=u（k-1）-（u（k-2）-（u（k-1））q（k-2））q（k-1）=.......这样的话依次用u（k-1）与u（k）的线性组合表示出了u（k+1）；用u（k-2）与u（k-1）的线性组合表示出了u（k+1）；.........最后用u（0），u（1）的线性组合表示出了u（k+1），因此，使得（1）成立的整数x，y存在

应用

1.若a |bc，且（a，b）=1，则ab |c

2.若a |c，b |c，且（a，b）=1，则ab |c

3.设m为正整数，则（ma，mb）=m（a，b），[ma，mb]=m[a，b]

4.设a，b都为正整数，则（a，b）·[a，b]=ab