欧几里得扩展

源网址 欧几里得扩展证明(自我感觉最好懂得一种写法) 欧几里得扩展公式 一定存在 x,y 使得

a∗x+b∗y=gcd(a,b) a ∗ x + b ∗ y = g c d ( a , b )

---

① ，当b = 0 时，gcd(a, b) = a , 此时 x = 1, y = 0;

---

② 当 a∗b≠0 a ∗ b ≠ 0 时，

设 a * x + b * y = gcd(a, b); (1)

b * x0 + (a % b) * y0 = gcd( b, a % b); (2)

由朴素的欧几里德公式; gcd(a, b) = gcd (b, a % b);

得(1)，(2)

a * x + b * y = b * x0 + (a % b) * y0 = b * x0 + (a – a / b * b) * y0 = a * y0 + ( x0 – a / b * y0 ) * b 所以 x = y0, y = x0 – a / b * y0;

由此可以得出扩展欧几里德的递归程序：

long long ext_gcd(long long a,long long b,LL &x,LL &y) { if(b==0) { x = 1,y = 0; return a; } LL m; m = ext_gcd(b,a%b,y,x); y -= a / b * x; return m; }

实际问题

在实际问题中，一般直接把a,b 先除以最大公约数

转化成

a1∗x+b1∗y=1 a 1 ∗ x + b 1 ∗ y = 1 这种形式思考比较容易 x=x+t∗b1; x = x + t ∗ b 1 ; y=y−t∗a1; y = y − t ∗ a 1 ;