欧几里得扩展

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

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

② 当 a∗b≠0 $a\ast b\ne 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 先除以最大公约数

转化成