『数论』扩展欧几里得算法

欧几里得算法

辗转相除计算两个数的最大公约数，求$gcd(a,b)$。

证明

设 $a=b×p+q$ ，则 $gcd(b,q)|b$ ， $gcd(b,q)|a$ ，故 $gcd(b,q)|gcd(a,b)$ .

同样 $q=a−b×p$ ，则 $gcd(a,b)|q$ ，故 $gcd(a,b)|gcd(b,q)$ .

可得 $gcd(a,b)=gcd(b,a)$ ，最终得到 $gcd(a,b)=gcd(c,0)=c$

代码

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

扩展欧几里得算法

存在整数对 $(x,y)$ 使得 $ax+by=gcd(a,b)$ .

证明

设 $a>b$ ,

当 $b=0$ 时， $a×1+b×0=a=gcd(a,b)$ ，此时 $x=1$ ， $y=0$

当 $b!=0$ 时，设

$a×x_1+b×y_1=gcd(a,b)$

$b×x_2+a\%b×y_2=gcd(b,a\%b)$

由于 $gcd(a,b)=gcd(b,a\%b)$ ，所以有 $a×x_1+b×y1=b×x_2+a\%b×y_2$

将 $a\%b=a−(a/b)×b$ 代入，

得到 $a×x_1+b×y_1=a×y_2+b×x_2−(a/b)×b×y_2$

即 $x_1=y_2,y_1=x_2−(a/b)×y_2$

因此可以递归的定义 $exgcd$ ，同样 $b=0$ 时递归结束，返回最大公约数。

代码

int extgcd(int a, int b, int &x, int &y)
{

    int d = a;
    if(b != 0) {
        d  = extgcd(b, a % b, y, x);
        y -= (a/b) * x;
    }else {
        x = 1, y = 0;
    }
    return d;
}

应用

求解不定方程

若 $c\%gcd(a,b)=0$ ，则存在整数对 $(x,y)$ ，使得 $a×x+b×y=c$

通过上面的方法可得到一组特解 $x_0$ ， $y_0$ 使得 $a×x_0+b×y_0=gcd(a,b)$ ，那么如何在无穷多个解中求出 $x$ ， $y$ 最小正整数解。

证明

首先 $a×x_0+a×k×b/gcd(a,b)+b×y_0−a×k×b/gcd(a,b)=gcd(a,b)$

即 $a×(x_0+k×b/gcd(a,b))+b×(y_0−k×a/gcd(a,b))=gcd(a,b)$

通解为 $x=x_0+k×b/gcd(a,b)$ ， $y=y_0−k×a/gcd(a,b)$ ，其中 $k=…−2,−1,0,1,2…$

在所有解中最小的正整数为 $(x_0+b/gcd(a,b))\%(b/gcd(a,b))$ ，

所以对于方程 $a×x+b×y=c$ ，最小正整数解（以x为例）为 $(x_0×c/gcd(a,b)+b/gcd(a,b))\%(b/gcd(a,b))$

注意：若 $b$ 为负数，需将 $b$ 转换为正数。

代码

int cal(int a, int b, int c)
{
    int x, y;
    int gcd = extgcd(a, b, x, y);
    if(c % gcd != 0) return -1;
    x *= c/gcd;
    b /= gcd;
    if(b < 0) b = -b;
    int ans = x % b;
    if(ans <= 0) ans += b;
    return ans;
}

同余方程

根据上面的内容，我们可以得到：

• $a×x≡b(mod~n)$ ，转化为 $a×x+n×y=b$ ，当 $b\%gcd(a,n)=0$ 时，方程有 $gcd(a,n)$ 个解。
• $a×x≡1(mod~n)$ ，如果 $gcd(a,n)=1$ ，则方程有唯一解。