博客推荐——直通车：http://blog.csdn.net/yukizzz/article/details/50642766
求：关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
下面证明中“→”表示等价于，“≡”表示同余，“/”表示向下取整。
∵ Ax ≡ 1 (mod m) → Ax mod m = 1 mod m
∴ 可表示 Ax = By + 1 → Ax - By = 1 即 求解x?
根据欧几里得扩展：
Ax + By = C = gcd(A, B)
∵ gcd(A, B) = gcd(B, A mod B)
∵ Bx’ + (A mod B)y’ = gcd(B, A mod B)
∴ Bx’ + (A mod B)y’ = gcd(A, B)
∴ Bx’ + (A - A/B * B)y’ = gcd(A, B)
→ Bx’ + Ay’ - B*(A/B)y’ = gcd(A, B)
→ Ay’ + B(x’ - (A/B)*y’) = gcd(A, B)
∴ x = y’, y = x’ -(A/B)*y’
前提是： Ax + By = gcd(A, B) 中，当B = 0 时，有x = 1,y = 0成立，证毕！
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 //辗转相除法 5 int ou(int a,int b,int &x,int &y) 6 { 7 if(b==0){ 8 x=1; 9 y=0; 10 return a; 11 } 12 int ans=ou(b,a%b,x,y); 13 int temp=x; 14 x=y,y=temp-a/b*y; 15 return ans; 16 } 17 18 int main() 19 { 20 int a1,b1,x1,y1; 21 cin>>a1>>b1; 22 int orz=ou(a1,b1,x1,y1); 23 while(x1<0) 24 { 25 x1+=(b1/orz); 26 } 27 cout<<x1<<endl; 28 return 0; 29 }
∵ Ax + By = C
当 x = x’ + B, 且 y = y’ - A
A(x’ + B) + B(y’ - A) = C
→ Ax’ + A*B + By’ - A*B = C
→ Ax’ + By’ = C
∴ 得出，原式不变。
扩展欧几里得：
扩展欧几里得算法：
找出一对整数（x，y），使得ax+by=gcd（a，b）
gcd（a，b）=gcd（b，a%b） 欧几里得定理
∴a x1 + b y1 = b x2 + （a%b）y2
∴a x1 + b y1 = b x2 + [a-（a/b）*b] y2 在整除意义下，a%b=a-（a/b）*b
∴a x1 + b y1 = b x2 + a y2 - b*（a/b）y2 右边展开
∴a x1 + b y1 = a y2 + b [x2 - （a/b）y2] 右边合并同类项
根据恒等定理得，x1 = y1 ，y1 = x2 - （a/b）y2
递归求解
边界条件：gcd（a，0）= 1 * a - 0 * 0 = a
void gcd(int a,int b,int &d,int &x,int &y)
{
if(!b) {d=a;a=1;y=0;}
else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
结论1：
设a，b，c 为任意整数。若 方程a x + b y = c 的一组整数解为（x0，y0）,
（前提：方程有解）
则它的任意整数解都可以写成（x0 + k b’，y0 - k a’）。
其中a’=a / gcd（a，b） b’=b / gcd（a，b），k取任意整数
证明：
由扩展欧几里得可以求出a x + b y = gcd （a，b）的一组解（x1，y1），
任取另外一组解 （x2，y2）
∴ a x1 + b y1 = a x2 + b y2
∴ a （x1 - x2） = b（y2 - y1）
令 a’= a / gcd（a，b） b’=b / gcd（a，b），那么 （a’，b’）= 1
∴ a’（x1 - x2） = b’ （y2 - y1）
∴ b’能整除（x1 - x2）
令 （x1 - x2） = k b’
则 （y2 - y1）= k a’
∴ x2 = x1 - k b’ y2 = k a’ + y1
推倒过程并没有用到 a x + b y 的 右边是什么 ，所以结论1 成立
结论1的前提是方程有解，那么什么情况下方程才有解？
对于方程 a x + b y = c
由上面已经推导出了 若 c=gcd（a，b），那么方程一定有解 （x，y）
若c！=gcd（a，b）
①、c是gcd（a，b）的倍数，令 c=gcd（a，b）*d
那么 （ a x + b y）/d = c /d = a * x / d + b * y / d = gcd （a，b） 方程有解（x’，y’）
x’ = x / d，y’ = y / d ∴x’=x c / g y’ = y c / g
②、c不是gcd（a，b）的倍数，那么无解
所以，结论2：
设a，b，c 为任意整数，g = gcd （a，b），方程 a x + b y = g 的一组解是 （x0，y0），
则当 c 是 g 的倍数时，ax + by = c 的一组解是 （x0 c / g ，y0 c / g）
自己选的路，跪着也要走完！！！