数学 - 扩展欧几里得算法

扩展欧几里得算法用于解决二元一次不定方程、一次同余方程、逆元等问题

二元一次不定方程

• 二元一次不定方程的定义：$$ax+by=c，(a,b,c\in Z且a,b\ne 0)\text{\hspace{1em}(1)}$$
• 如果$c=0$，则方程的整数解为：$x=-bt，y=at，(t\in Z)$
• 如果$c$为负数，则(1)式两边乘以$-1$，等号右边就变成正整数；因为所求的$x$，$y$可正可负，所以我们只用讨论$a$，$b$是正整数的情况。
• 设$d$为$a$和$b$的最大公因数，即 d = g c d ( a , b ) ， a =a1 ∗ d ， b =b1 ∗ d ， (a1 ,b1 ) = 1 d = gcd(a, b)，a = a_1 * d，b = b_1 * d，(a_1, b_1) = 1 d=gcd(a,b)，a=a1​∗d，b=b1​∗d，(a1​,b1​)=1，则(1)式变为 d ∗ ( a 1 x + b 1 x ) = c (2) d * (a_1x + b_1x) = c \tag{2}d∗(a1​x+b1​x)=c(2)

结论：当 $d\nmid c$ 时，(1)式没有整数解；当 $d\mid c$ 时，(1)式一定有整数解，这可以通过贝祖定理（又称裴蜀定理）得到。

贝祖定理：如果$a$和$b$是整数，且 $gcd(a,b)=d$，那么对于任意的整数$x，y，ax+by$都一定是$d$的倍数；特别的，一定存在整数$x，y$，使$ax+by=d$成立。

• 贝祖定理的一个重要推论是：$a$和$b$互质的充分必要条件是存在整数$x，y$，使$ax+by=1$
• $ax+by$能够得到的最小结果就是它们的最小公倍数

我们通过几个例子，解释$x$和$y$的求解步骤，并在此基础上得出扩展欧几里得算法。

例1：$17x+5y=1$

$\because gcd(17,5)=1，\therefore 方程有解$

$(3\ast 5+2)x+5y=1$，整理得：
$5(3x+y)+2x=1$
用换元法，如果我们求出如下方程的解，
5 x ′ + 2 y ′ = 1 5x^{'} + 2y^{'} = 1 5x′+2y′=1，则： x = y ′ ， y = x ′ − 3 y ′ x = y^{'}，y = x^{'} - 3y^{'} x=y′，y=x′−3y′

( 2 ∗ 2 + 1 ) x ′ + 2 y ′ = 1 (2*2 + 1)x^{'} + 2y^{'} = 1 (2∗2+1)x′+2y′=1，整理得：
2 ( 2 x ′ + y ′ ) + x ′ = 1 2(2x^{'} + y^{'}) + x^{'} = 1 2(2x′+y′)+x′=1
用换元法，如果我们求出如下方程的解，
2 x ′ ′+ y ′ ′= 1 2x^{''} + y^{''} = 1 2x′′+y′′=1，则： x ′ = y ′ ′， y ′ = x ′ ′− 2 y ′ ′ x^{'} = y^{''}，y^{'} = x^{''} - 2y^{''} x′=y′′，y′=x′′−2y′′

( 2 ∗ 1 + 0 ) x ′ ′+ y ′ ′= 1 (2*1 + 0)x^{''} + y^{''} = 1 (2∗1+0)x′′+y′′=1，整理得：
1 ( 2 x ′ ′+ y ′ ′) + 0 x ′ ′= 1 1(2x^{''} + y^{''}) + 0x^{''} = 1 1(2x′′+y′′)+0x′′=1
用换元法，如果我们求出如下方程的解，
1 x ′ ′ ′+ 0 y ′ ′ ′= 1 1x^{'''} + 0y^{'''} = 1 1x′′′+0y′′′=1，则： x ′ ′= y ′ ′ ′， y ′ ′= x ′ ′ ′− 2 y ′ ′ ′ x^{''} = y^{'''}，y^{''} = x^{'''} - 2y^{'''} x′′=y′′′，y′′=x′′′−2y′′′

显而易见，方程 1 x ′ ′ ′+ 0 y ′ ′ ′= 1 1x^{'''} + 0y^{'''} = 1 1x′′′+0y′′′=1 有解 x ′ ′ ′= 1 ， y ′ ′ ′= 0 x^{'''} = 1，y^{'''} = 0 x′′′=1，y′′′=0。
x ′ ′ ′ x^{'''} x′′′的系数$1$，就是原方程中$17$和$5$的最大公约数

回溯可得，
x ′ ′= 0 ， y ′ ′= 1 x^{''} = 0，y^{''} = 1 x′′=0，y′′=1
x ′ = 1 ， y ′ = − 2 x^{'} = 1，y^{'} = -2 x′=1，y′=−2
$x=-2，y=7$

例2：$27x+21y=3$

$\because gcd(27,21)=3，\therefore 方程有解$

$(1\ast 21+6)x+21y=3$，整理得：
$21(x+y)+6x=3$
用换元法，如果我们求出如下方程的解，
21 x ′ + 6 y ′ = 3 21x^{'} + 6y^{'} = 3 21x′+6y′=3，则： x = y ′ ， y = x ′ − y ′ x = y^{'}，y = x^{'} - y^{'} x=y′，y=x′−y′

( 3 ∗ 6 + 3 ) x ′ + 6 y ′ = 3 (3*6 + 3)x^{'} + 6y^{'} = 3 (3∗6+3)x′+6y′=3，整理得：
6 ( 3 x ′ + y ′ ) + 3 x ′ = 3 6(3x^{'} + y^{'}) + 3x^{'} = 3 6(3x′+y′)+3x′=3
用换元法，如果我们求出如下方程的解，
6 x ′ ′+ 3 y ′ ′= 3 6x^{''} + 3y^{''} = 3 6x′′+3y′′=3，则： x ′ = y ′ ′， y ′ = x ′ ′− 3 y ′ ′ x^{'} = y^{''}，y^{'} = x^{''} - 3y^{''} x′=y′′，y′=x′′−3y′′

( 2 ∗ 3 + 0 ) x ′ ′+ 3 y ′ ′= 3 (2*3 + 0)x^{''} + 3y^{''} = 3 (2∗3+0)x′′+3y′′=3，整理得：
3 ( 2 x ′ ′+ y ′ ′) + 0 x ′ ′= 3 3(2x^{''} + y^{''}) + 0x^{''} = 3 3(2x′′+y′′)+0x′′=3
用换元法，如果我们求出如下方程的解，
3 x ′ ′ ′+ 0 y ′ ′ ′= 3 3x^{'''} + 0y^{'''} = 3 3x′′′+0y′′′=3，则： x ′ ′= y ′ ′ ′， y ′ ′= x ′ ′ ′− 2 y ′ ′ ′ x^{''} = y^{'''}，y^{''} = x^{'''} - 2y^{'''} x′′=y′′′，y′′=x′′′−2y′′′

显而易见，方程 3 x ′ ′ ′+ 0 y ′ ′ ′= 3 3x^{'''} + 0y^{'''} = 3 3x′′′+0y′′′=3 有解 x ′ ′ ′= 1 ， y ′ ′ ′= 0 x^{'''} = 1，y^{'''} = 0 x′′′=1，y′′′=0。
x ′ ′ ′ x^{'''} x′′′的系数$3$，就是原方程中$27$和$21$的最大公约数

回溯可得，
x ′ ′= 0 ， y ′ ′= 1 x^{''} = 0，y^{''} = 1 x′′=0，y′′=1
x ′ = 1 ， y ′ = − 3 x^{'} = 1，y^{'} = -3 x′=1，y′=−3
$x=-3，y=4$

对于方程：$ax+by=gcd(a,b)$

$(\lfloor a/b\rfloor \ast b+a\%b)x+by=gcd(a,b)$，整理得：
$b(\lfloor a/b\rfloor \ast x+y)+a\%b\ast x=gcd(a,b)$
用换元法，如果我们求出如下方程的解，
b ∗ x ′ + a % b ∗ y ′ = g c d ( a , b ) b * x^{'} + a \% b * y^{'} = gcd(a, b) b∗x′+a%b∗y′=gcd(a,b)，则： x = y ′ ， y = x ′ − ⌊ a / b ⌋ ∗ y ′ x = y^{'}，y = x^{'} - \lfloor a/b \rfloor * y^{'} x=y′，y=x′−⌊a/b⌋∗y′

不断递归，最后我们得到方程：
g c d ( a , b ) ∗ x ~ + 0 ∗ y ~ = g c d ( a , b ) gcd(a, b) * \tilde x + 0 * \tilde y = gcd(a, b) gcd(a,b)∗x~+0∗y~​=gcd(a,b)，

可得该方程的一组解： x ~ = 1 ， y ~ = 0 \tilde x = 1，\tilde y = 0 x~=1，y~​=0。
x ~ \tilde x x~的系数，就是原方程中$a$和$b$的最大公约数

不断回溯，最后得到原方程的解

扩展欧几里得算法的参考代码：

//二元一次不定方程：ax + by = gcd(a, b)//函数返回 gcd(a, b)；通过引用传递，返回一组解 (x, y)int exgcd(int a, int b, int &x, int &y) {    if (b == 0) { x = 1, y = 0; return a;    }    int gcd = exgcd(b, a % b, x, y);    int t = x;    x = y;    y = t - a / b * y;    return gcd;}

总结：

对于一般情况，$ax+by=c$，($a,b,c$为正整数)，设 $d=gcd(a,b)$

• 如果$d\nmid c$，方程无解
• 如果$d\mid c$，
  • 先求出方程$ax+by=d$的一组解 x 0, y 0x_0, y_0 x0​,y0​
  • 原方程的一组解为 x ′ = x 0∗ c / d ， y ′ = y 0∗ c / d x^{'} = x_0 * c/d，y^{'} = y_0 * c/d x′=x0​∗c/d，y′=y0​∗c/d
  • 原方程的通解为 x = x ′ + k ∗ b / d ， y = y ′ − k ∗ a / d x = x^{'} + k * b / d，y = y^{'} - k * a / d x=x′+k∗b/d，y=y′−k∗a/d，$k$为任意整数
  • 设$p=b/d$，$x$的最小非负整数解为 ( x ′ %   p + p )   %   p (x^{'} \% \ p + p) \ \% \ p (x′% p+p) % p
  • 设$q=a/d$，$y$的最小非负整数解为 ( y ′ %   q + q )   %   q (y^{'} \% \ q + q) \ \% \ q (y′% q+q) % q

求解一次同余方程 $ax\equiv b(modm)$

• 一次同余方程亦称线性同余方程，指未知数仅出现一次幂的同余方程。
• 该同余方程等价于 $ax=m\ast (-y)+b$，即$ax+my=b$
• 如果$gcd(a,m)\nmid b$，该方程无解
• 如果$gcd(a,m)\mid b$，用上述方法求解

求解乘法逆元

• 对于正整数$a,m$，如果有$ax\equiv 1(modm)$，则称$x$的最小正整数解为$a$模$m$的逆元，也叫做数论倒数，记作 a − 1a^{-1} a−1。$a$和$x$一定都和$m$互质，如果$a$和$m$不互质就不存在逆元。
• 乘法运算中a ∗a − 1 = 1 a * a^{-1} = 1 a∗a−1=1，模运算中，a ∗a − 1 ≡ 1   ( m o d   m ) a * a^{-1} \equiv 1 \ (mod \ m) a∗a−1≡1 (mod m)

扩展欧几里得算法求逆元：

• 见求解一次同余方程

费马小定理求逆元：

• 如果模数$m$为质数，可利用费马小定理求逆元： a m − 1 ≡ 1   ( m o d   m ) a^{m-1} \equiv 1 \ (mod \ m) am−1≡1 (mod m)
• 因为a ∗a m − 2 ≡ 1   ( m o d   m ) a * a^{m-2} \equiv 1 \ (mod \ m) a∗am−2≡1 (mod m)，所以$a$的逆元是 a m − 2   % m a^{m-2} \ \% m am−2 %m，用快速幂计算
• 例如，$m$为7时，3 ∗35 ≡ 1   ( m o d   7 ) 3 * 3^5 \equiv 1 \ (mod \ 7) 3∗35≡1 (mod 7)， 35   %   7 3^5 \ \% \ 7 35 % 7为$3$模$7$的逆元

欧拉函数求逆元：

• 欧拉定理：如果$a$和$m$互质，设$\varphi (m)$为小于$m$且与$m$互质的正整数的个数，则有 a ϕ ( m ) ≡ 1   ( m o d   m ) a^{\phi(m)} \equiv 1 \ (mod \ m) aϕ(m)≡1 (mod m)
• 因为a ∗a ϕ ( m ) − 1 ≡ 1   ( m o d   m ) a * a ^ {\phi(m) - 1} \equiv 1 \ (mod \ m) a∗aϕ(m)−1≡1 (mod m)，所以$a$的逆元是 a ϕ ( m ) − 1   % m a^{\phi(m)-1} \ \% m aϕ(m)−1 %m，用快速幂计算
• $m$可以不是质数
• 例如，$m$为8时，$\varphi (8)=4$，3 ∗33 ≡ 1   ( m o d   8 ) 3 * 3^3 \equiv 1 \ (mod \ 8) 3∗33≡1 (mod 8)， 33   %   8 3^3 \ \% \ 8 33 % 8为$3$模$8$的逆元

逆元的用处：

• 取余运算有如下性质
  • $(a+b)\%m=(a\%m+b\%m)\%m$
  • $(a-b)\%m=(a\%m-b\%m)\%m$
  • $(a\ast b)\%m=(a\%m\ast b\%m)\%m$
  • a b  % m = ( a % m ) b  % m a^b \ \% m = (a \% m)^b \ \%m ab %m=(a%m)b %m
• 但对除法不成立
  • $(a/b)\%m\ne (a\%m/b\%m)\%m$
  • 例如，$ (8 / 2) % 7 = 4$，而$ (8 % 7) / (2 % 7) % 7 = 0$
• 如果$b\mid a$，则( a   /   b ) % m = ( a   /   b ) ∗ ( b ∗b − 1 ) % m = ( a / b ∗ b ) ∗ (b − 1 ) % m = ( a ∗b − 1 ) % m (a \ / \ b) \% m = (a \ / \ b) * (b * b^{-1}) \% m = (a / b * b) * (b^{-1}) \% m = (a * b^{-1}) \% m (a / b)%m=(a / b)∗(b∗b−1)%m=(a/b∗b)∗(b−1)%m=(a∗b−1)%m。这样我们就把除法取余运算转化成了乘法取余运算。
• 例如，求3的幂的和