扩展欧几里得算法

定义

扩展欧几里得算法用于已知\(a,b\)，求解一组\(x,y\)，使得他们满足\(ax+by=\gcd(a,b)=d\)。

有关概念

1. 设\(a,b\)是整数，则一定存在\(x,y\)，使得方程\(ax+by=m\)有解，其中\(m\)满足\(\gcd(a,b)|m\)。称之为裴蜀定理（贝祖定理）。

求解算法

思路与简单证明

首先设\(ax_1+by_1=\gcd(a,b)\),\(bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\)。

根据欧几里得算法，

\(\gcd(a,b)=\gcd(b,a\bmod b)\)；

故\(ax_1+by_1=bx_2+(a\bmod b)y_2\)；

得\(ax_1+by_1=bx_2+(a-\lfloor \frac ab\rfloor\times b)y_2\)；

得\(ax_1+by_1=ay_2+b(x_2-\lfloor \frac ab\rfloor y_2)\)；

根据多项式恒等定理，得：

\(x_1=y_2,y_1=x_2-\lfloor \frac ab\rfloor y_2\)

于是我们发现，可以按照类似欧几里得算法的形式递归求解，边界条件：

当\(b=0\)时，\(\gcd(a,b)=a\)，此时方程的解为\(x=1,y=0\)。

实现

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return d;
}

应用

1. 求解线性同余方程\(ax+by=c\)：

   首先该方程需满足\(\gcd(a,b)|c\)，否则无解。

   先用扩展欧几里得算法求出方程\(ax+by=\gcd(a,b)\)的一组解\(x_0,y_0\)，该方程的任意一组解可以表示为\(x=x_0+\frac b{\gcd(a,b)}t,y=y_0-\frac a{\gcd(a,b)}t,\ t\in Z\)。将等号两边同时同时乘以\(\frac c {\gcd (a,b)}\)，就求得了原方程的一个解。

   方程通解的证明：

   若有\(ax+by=d\)且\(a_0x+b_0y=d\)

   那么便有\(a(x-x_0)+b(y-y_0)=0\)

   两边同时除以\(\gcd(a,b)\)可得：

   \(\frac{a}{\gcd(a,b)}(x-x_0)=-\frac{b}{\gcd(a,b)}(y-y_0)\)

   而因为\(\gcd(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)})=1\)

   所以可得\(\frac{b}{\gcd(a,b)}|(x-x_0)\)

   所以很显然有\(\frac{b}{\gcd(a,b)}t=(x-x_0),t \in Z\)