对任意整数 a , b , d , (a , b) | d ，存在整数 u , v 使得 ua + vb = d
扩展欧几里得
$$\displaystyle a\mod b = a - \lfloor{\frac{a}{b}}\rfloor b$$
由归纳法假设存在 u’ , v’ 使得 u’ b + v’ (a mod b) = d
即
$$\displaystyle u’b + v’(a - \lfloor{\frac{a}{b}}\rfloor) b = d$$
$$\displaystyle v’a + (u’ - \lfloor{\frac{a}{b}}\rfloor v’) b = d$$
于是就有了 (a,b) 的解。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
intexgcd(int a,int b,int &x,int &y){ if(b == 0) { x = 1; y = 0; return a; } // int xx,yy; // int d = exgcd(b,a % b,xx,yy); // x = yy; // y = xx - (a / b) * yy;
int d = exgcd(b,a % b, y, x); y -= (a / b) * x; return d; }