拓展欧几里得

发表于 更新于

一个晚上的成果。 # 背景 ### 贝祖定理： 如果\(a\)、\(b\)是整数，那么一定存在整数\(x\)，\(y\)使得\(ax+by=gcd(a,b)\)。

证明：

  1. 若任何一个等于\(0\)，则\(gcd(a,b)=a\)，这时定理显然成立
  2. 若\(a,b\)不等于0. 由于\(gcd(a,b)=gcd(a,-b)\), 不妨设\(a,b\)都大于0，\(a\ge b,gcd(a,b)=d.\) 对\(ax+by=d\)，两边同时除以\(d\),可得\(a_1x+b_1y=1\),其中\((a_1,b_1)=1\). 转证\(a_1x+b_1y=1\). 我们先回顾一下辗转相除法是怎么做的，由\(gcd(a,b)\longrightarrow gcd(b,a mod b)\longrightarrow...\)我们把模出来的数据叫做\(r\) 于是有： \[ gcd(a_1,b_1)=gcd(b_1,r_1)=gcd(r_1,r_2)=...=gcd(r_{n-1},r_n)=1 \]

把辗转相除法中的运算展开，做成带余数的除法，得 \[ a_1=q_1b_1+r_1(0\le r_1 <b_1) \\ b_1=q_2r_1+r_2(0\le r_2 <r_1) \\ r_1=q_3r_2+r_3 (0\le r_3 <b_2)\\ ... \\r_{n-3}=q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2}=q_nr_{n-1}+r_n\\r_{n-1}=q_{n+1}r_{n} \] 不妨令辗转相除法在除到互质的时候退出则\(r_n=1\) （\(q\)被换成了\(x\),为了符合最终形式） \[ r_{n-2}=x_nr_{n-1}+1 \] 即 \[ 1=r_{n-2}-x_nr_{n-1} \] 由倒数第三个式子\(r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}\)代入上式，得 \[ 1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} \] 然后用同样的方法用它上面的等式逐个的消去\(r_{n-2},...,r_1\),

可证得\(1=a_1x+b_1y\).这样等于是一般式中\(d=1\)的情况

欧几里得算法

即辗转相除法，它的代码非常简单：

1
2
3
4
5
6
7
8
//辗转相除法，求两个数的最大公因数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}

拓展欧几里得算法

扩展欧几里得算法用来解决这样一个问题：给定两个非零的整数\(a\)和\(b\)，求一组整数解\((x，y)\)使得\(ax+by = gcd(a,b)\)成立，其中\(gcd(a,b)\)表示\(a\)和\(b\)的最大公约数。（其中我们通过前面的贝祖定理可知解一定存在）

回忆我们知道的欧几里得算法，它总是把\(gcd(a,b)\)转化为求解\(gcd(b,a%b)\)，而当\(b\)变为\(0\)时返回\(a\)，此时的\(a\)就等于\(gcd\)。也就是说，欧几里得算法结束时变量\(a\)中存放的是\(gcd\)，变量\(b\)中存放的是\(0\)，因此此时显然有\(a × 1 + b × 0 = g c d\)成立，此时有\(x=1\)、\(y=0\)成立。

我们不妨利用上面的欧几里得算法的过程来计算\(x\)和\(y\)。目前已知的是递归边界成立时为\(x=1\)、\(y=0\)，需要想办法反推出最初始的\(x\)和\(y\)。

对比等号左右两边可以马上得到下面的递推公式： \[ \begin{cases}x_1=y_2\\y_1=x_2-(a/b)y_2\end{cases} \] 由此可以通过\(x_2\)和\(y_2\)来进行反推出\(x_1\)和\(y_1\)了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int exGcd(int a, int b, int &x, int &y)   //x和y使用引用
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int g = exGcd(b, a%b, x, y);    //递归计算exGcd（b,a%b）
    int temp = x;             //存放x的值
    x = y;
    y = temp - (a/b)*y;       //更新y = x(old) - a/b*y(old)
    return g;                 //g是gcd
}

由于这里我们使用了引用，因此当 \(exGcd\) 函数结束时 \(x\) 和 \(y\) 就是所求的解。

显然，在得到这样一组解之后，就可以通过下面的式子得到全部解（其中 \(K\) 为任意整数）： \[ \begin{cases}x^{'}=x+\frac {b}{gcd}\times K\\y^{'}=y-\frac {a}{gcd}\times K\end{cases} \]