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

欧几里得算法

辗转相除计算两个数的最大公约数,求$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$ ,则方程有唯一解。

  • 2 只已被捕捉
    • 韭菜韭菜 Chrome | 54.0.2840.59 Windows 10

      • 千千 Mozilla FireFox | 51.0 Windows 10

        怎么啦