扩展欧几里德定理

引入

对于不定方程 $ax+by=c$，如果我们想求出它的整数解，我们就可以使用扩展欧几里德定理(exgcd)。

前置知识

裴蜀定理

定义

设 $a$, $b$ 是不全为零的整数，则存在整数 $x$, $y$ 使得 $\textit{ax+by=gcd(a,b)}$.

证明

1. 当 $a = 0$ 或 $b = 0$ 时，原式显然成立
2. 当 $a, b$ 都不等于 $0$ 时
   • 记集合 $S = \{ax + by| x,y \in Z且ax + by > 0\}$
   • 设 $d=ax_0+by_0$ 为 $S$ 中的最小正整数，现在只需证明 $d=gcd(a,b)$即可
   • 设 $a = qd+r$，其中 $q, r$ 分别为 $a/d$ 的商和余数，则有
   • $r=a-qd=a-q(ax_0+by_0)=a(1-qx_0)+b(-qy_0)$，注意到形式一致，说明 $r$ 也是 $S$ 中的元素，又 $d$ 为最小正整数，故 $r = 0$ ，即 $d|a$
   • 同理可得，$d|b$ ，故 $d|gcd(a,b)$，又 $gcd(a,b) | ax_0+by_0$ ，故 $d=gcd(a,b)$，证毕

扩展欧几里德定理

接下来，让我们讲解一下扩展欧几里德定理(exgcd):

• 设 $ax_1+by_1=gcd(a,b)$，$bx_2+(a\ mod\ b)y_2=gcd(b,a\ mod\ b)$
• 由欧几里德定理可知，$gcd(a,b)=gcd(b,a\ mod\ b)$，且 $a\ mod\ b = a-\lfloor a/b\rfloor * b$
• 故 $ax_1+by_1=bx_2+(a-\lfloor a/b\rfloor * b)y_2 = ay_2+b(x_2-\lfloor a/b\rfloor y_2)$
• 故$x_1=y_2$，$y_1=x_2-\lfloor a/b\rfloor y_2$，到这里，我们遍可以递归求解了，注意退出条件：当 $b=0$ 时，$x=1$，$y=0$

核心代码如下：

1
2
3
4
5
6
7
8
9
10

void exgcd(int a, int b, int &x, int &y) //x,y通过引用的形式传入，以便直接更改值
{
    if(!b)
    {
        x = 1;
        y = 0;
	}
    exgcd(b, a%b, y, x);
    y -= a/b * x;
}

可能有人会问：y -= a/b * x是什么意思呢？

• 我们不妨假设递归结束时 $x=x_n$，$y=y_n$ ，那么退回到上一层后有：$y_{n-1}=x_n$，$x_{n-1}=y_n$
• 由前文我们知道，$x_{n-1}=y_n$，$y_{n-1}=x_n-\lfloor a/b\rfloor y_n$，所以退回上一层后 $x_{n-1}$ 直接被求得
• 而对于 $y_{n-1}$ ，我们发现 $x_n=y_{n-1}$ ，$y_n=x_{n-1}$，所以 $y_{n-1} =y_{n-1}-\lfloor a/b\rfloor x_{n-1}$ ，即原代码所示

延伸

现在我们通过扩展欧几里德定理求出了原方程的一组解，那我们能不能求出其通解呢？答案是可以的

• 设exgcd求出的一组解为 $(x_1,y_1)$ ，待求的另一组解为 $(x_2,y_2)$
• 则有 $ax_1+by_1=ax_2+by_2$ ，整理得 $a(x_1-x_2)=b(y_2-y_1)$
• 两边同时除以 $gcd(a,b)$，得 $a^{\prime}(x_1-x_2)=b^{\prime}(y_2-y_1)$，其中 $a^{\prime} = a/gcd(a,b)$，$b^{\prime} = b/gcd(a,b)$
• 由于 $a^{\prime}$ 与 $b^{\prime}$ 互质，故 $x_1-x_2$ 为 $b^{\prime}$ 的整数倍，即 $x_1-x_2 = kb^{\prime}$ ，故 $x_2=x_1-kb^{\prime}$ ，同理，$y_2=y_1+ka^{\prime}$
• 故原方程的通解为 $x = x_1-kb/gcd(a,b)$ ，$y=y_1+ka/gcd(a,b)$