所谓贝祖定理是说：
两个整数 a、b 是互质的。等价于方程 ax+by=1有整数解。
当然。 贝祖定理另一种更一般的形式，说的是两个整数 a、b有最大公因数是c，等价于方程 ax+by=c有整数解。
这两种表述事实上是等价的。由于对另外一种形式略微一变形就得到了：
所以我们仅仅须要考虑第一种形式的贝祖定理就能够了。
贝祖定理的证明并不复杂。只是由于不管是中学还是大学（除了数学专业）都非常少讨论这类跟数论相关的问题，所以可能有些人会感觉这个问题有些无从下手。
这里先给个贝祖定理的简单证明。
首先，很easy就能够证明a、b 假设不互质。那么 ax+by=1无整数解。因此我们仅仅须要考虑a、b 是互质的这样的情况。
当x、y取不同整数值时。ax+by 也会有不同的结果，这些结果中最小的那个正整数设为s，也就是
ax+by=s
设a整除s 的商为q，余数为r。也就是
那么
如果 r 不等于0就与我们如果s为ax+by这个集合的最小的正整数矛盾了。所以r仅仅能等于0，也就是说a能够整除s。同理也能够证明b能够整除s。这说明s是a和b的公约数，而我们知道a和b是互质的，所以s仅仅能等于1。这就证明了贝祖定理。
怎样计算x、y的值是还有一个问题，当然我们知道x、y有无数多组整数解。我们仅仅须要求出一组解就够了。
不失一般性，我们设 a > b。a = bq+r
能够看到。我们将 ax+by=1转化为 ax+by'=1当中d比a要小。这个过程能够一直反复，直到当中一个整数等于1。
方程变类似形式：
ex+y=1
这时仅仅要让x=0，y=1 就能够了。然后一步步回带，就能求得最初的x、y了。
这是一个典型的递归的过程。
以下给个C语言实现的代码。代码比較简单，就没有加入凝视：
bool Bezout(int a, int b, int *px, int *py) { int q, r; int x, y; bool ok; if( a == 1 ) { *px = 1; *py = 0; return true; } if( b == 1 ) { *px = 0; *py = 1; return true; } if( a >= b ) { q = a / b; r = a % b; if ( r == 0 ) { return false; } ok = Bezout(r, b, &x, &y); if( ok ) { *px = x; *py = y - q * x; } return ok; } else { q = b / a; r = b % a; if ( r == 0 ) { return false; } ok = Bezout(a, r, &x, &y); if( ok ) { *py = y; *px = x - q * y; } return ok; } return true; }
这里是測试用例：
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> bool Bezout(int a, int b, int *px, int *py); int main() { int x, y; int a = 73; int b = 32; bool ok; ok = Bezout(a, b, &x, &y); if(ok) { printf("%d * %d + %d * %d = %d, is ok\n", a, x, b, y, a * x + b * y); } return 0; }转载于:https://www.cnblogs.com/bhlsheji/p/5355417.html
相关资源：数据结构—成绩单生成器