拓展欧几里得

前置知识

最大公约数

GCD与LCM

模运算

模运算的基本规则与四则运算基本一致:
img
为什么没有除法,是因为除法在这里比较特别。

同余

概念

如果 $a$ 和 $b$ 除以 $c$ 的余数相同,就说 $a$ 和 $b$ 关于模 $c$ 同余,记作 $a \equiv b \pmod{c}$。 > 如果 $a$ 和 $b$ 的差能够被 $m$ 整除,那么就说 $a$ 和 $b$ 关于 $m$ 同余。

同余关系是一种等价关系

  1. 自反性:一个数永远和本身同余
  2. 对称性:$a$ 和 $b$ 同余,$b$ 和 $a$ 也同余
  3. 传递性:$a$ 和 $b$ 同余,$b$ 和 $c$ 也同余,即可推出 $a$ 和 $c$ 也同余

线性同余方程

给定整数 $a$、$b$ 和 $m$,线性同余方程 $ax \equiv b \pmod{m}$ 的解是一个整数 $x$,使得 $ax$ 和 $b$ 对 $m$ 取模后的结果相同。 要解决线性同余方程,可以使用拓展欧几里得算法来找到解。如果 $\text{gcd}(a, m)$ 能够整除 $b$,那么方程 $ax \equiv b \pmod{m}$ 有解,否则无解。
解法:

  1. 使用拓展欧几里得算法找到整数 $x’$ 和 $y’$,使得 $ax’ + my’ = \text{gcd}(a, m)$。
  2. 如果 $\text{gcd}(a, m)$ 能够整除 $b$,那么方程 $ax \equiv b \pmod{m}$ 有解,且一组解为:$x = x’ \times \frac{b}{\text{gcd}(a, m)}$。

裴蜀定理

裴蜀定理(Bézout’s Lemma)是说,对于任意给定的两个整数 $a$ 和 $b$,存在整数 $x$ 和 $y$,使得它们满足以下等式: $$ ax + by = \text{gcd}(a, b) $$ 这个定理是拓展欧几里得算法的基础,通过这个定理,我们可以求解线性同余方程 $ax + by = c$ 的整数解。

裴蜀定理证明:

基本情况: 当 $b=0$ 时,我们有 $\text{gcd}(a, 0) = a$。此时,等式 $ax + 0 = a$ 显然成立,其中 $x=1$。

归纳假设: 假设对于某些整数 $k$,当 $b < k$ 时,裴蜀定理成立,即存在整数 $x$ 和 $y$,使得 $ax + by = \text{gcd}(a, b)$。

归纳步骤: 现在考虑 $b=k$ 的情况。我们使用带余除法,将 $a$ 除以 $k$ 得到余数 $r$。根据带余除法,我们有:

$$
a = qk + r
$$

其中,$q$ 是商,$r$ 是余数,$0 \leq r < k$。

因为 $r = a - qk$,所以 $r$ 是 $a$ 和 $k$ 的线性组合。根据归纳假设,我们知道存在整数 $x’$ 和 $y’$,使得:

$$
kx’ + ry’ = \text{gcd}(k, r)
$$

将 $r$ 代入,我们有:

$$
kx’ + (a - qk)y’ = \text{gcd}(k, a)
$$

$$
ay’ + k(x’ - qy’) = \text{gcd}(k, a)
$$

这表明 $\text{gcd}(a, k) = \text{gcd}(k, r)$。

因此,通过归纳法,我们证明了对于任意的整数 $a$ 和 $b$,存在整数 $x$ 和 $y$,使得它们满足裴蜀定理。

这就完成了裴蜀定理的证明。

费马小定理

费马小定理是数论中的一条重要定理,由法国数学家皮埃尔·德·费马在17世纪提出。它的表述如下:

定理: 如果 $p$ 是一个素数,$a$ 是任意整数且不是 $p$ 的倍数,那么以下等式成立:

$$
a^{p-1} \equiv 1 \pmod{p}
$$

其中,$\equiv$ 表示模同余。

这个定理的一个直接推论是:如果 $p$ 是一个素数,$a$ 是任意整数,那么 $a^p \equiv a \pmod{p}$。

应用

费马小定理在密码学、编程竞赛中的算法设计等领域有着重要应用。

  1. 模幂运算: 费马小定理提供了一种快速计算模幂的方法。在计算 $a^b \pmod{p}$ 时,可以先使用费马小定理将指数化简,然后再进行模幂运算,大大提高了计算效率。

  2. 模反元素: 如果需要求解模方程 $ax \equiv 1 \pmod{p}$,即求解关于 $x$ 的同余方程的解,其中 $p$ 是素数,那么根据费马小定理,$x \equiv a^{p-2} \pmod{p}$ 就是方程的解。这提供了一种高效的方法来求解模反元素。

  3. 素性检测: 费马小定理可以作为素性检测算法的一部分。在 Miller-Rabin 素性检测算法中,利用费马小定理判断一个数是否为素数。

注意事项

在应用费马小定理时,需要注意选择合适的素数 $p$,以及确保 $a$ 不是 $p$ 的倍数,否则定理可能不成立。

推论

费马小定理的一个重要推论是,对于任意整数 $a$、$b$ 和素数 $p$,如果 $\text{gcd}(a, p) = 1$,那么以下等式成立:

$$
a^{p-1} \equiv 1 \pmod{p}
$$

将 $a^{p-1}$ 写成 $a \times a^{p-2}$,并将等式两边同时乘以 $b^{p-2}$,得到:

$$
a^{p-1} \times b^{p-2} \equiv b^{p-2} \pmod{p}
$$

再将 $a^{p-1}$ 和 $b^{p-2}$ 替换成它们的原式,得到:

$$
ab^{p-1} \equiv b^{p-1} \pmod{p}
$$

由于 $b^{p-1} \equiv 1 \pmod{p}$(根据费马小定理),所以:

$$
ab^{p-1} \equiv b^{p-1} \equiv 1 \pmod{p}
$$

即,

$$
ab^{p-1} - 1 \equiv 0 \pmod{p}
$$

现在我们有一个形式为 $ax - 1 \equiv 0 \pmod{p}$ 的方程,其中 $x = b^{p-1}$。如果我们令 $y = p-1$,那么我们得到的方程就是 $ax - py = 1$,这与裴蜀定理的形式完全相同。因此,我们可以利用费马小定理来求解形如 $ax + by = \text{gcd}(a, b)$ 的线性同余方程。

逆元

什么是逆元

在模运算中,对于整数 $a$ 和模数 $m$,如果存在整数 $a^{-1}$,使得 $a \times x \equiv 1 \pmod{m}$,那么 $x$ 就是 $a$ 在模 $m$ 意义下的逆元。逆元通常用符号 $a^{-1}$ 表示。

快速幂算法

快速幂

快速幂算法是一种高效计算幂的方法,它可以在对数时间复杂度内计算出 $a^b \mod m$ 的值。在计算逆元时,我们可以利用费马小定理:

如果 $p$ 是一个素数,$a$ 是一个整数,且 $a$ 不是 $p$ 的倍数,那么
$a^{p-1} \equiv 1 \pmod{p}$
$a^{p-2} \equiv a^{-1} \pmod{p}$

所以,$a$ 的逆元 $a^{-1}$ 就是 $a^{p-2} \mod p$。

拓展欧几里得算法

拓展欧几里得算法用于解决形如 $ax + by = \text{gcd}(a, b)$ 的等式。当 $a$ 和 $b$ 互质时,这个算法可以用来计算 $a$ 的模 $b$ 的逆元。

假设我们要计算 $a^{-1} \pmod{m}$,其中 $\text{gcd}(a, m) = 1$,则可以通过拓展欧几里得算法找到一对整数 $x$ 和 $y$,使得:
$ax + my = 1$
对两边同时取模 $m$,我们得到:
$ax \equiv 1 \pmod{m}$

拓展欧几里得算法

拓展欧几里得算法是用于求解一元线性同余方程 ax ≡ b (mod m) 的一种有效方法。与普通的欧几里得算法相比,拓展欧几里得算法不仅可以找到方程 ax + my = gcd(a,m) 的整数解 xy,还可以根据这个解得到同余方程 ax ≡ b (mod m) 的解。

拓展欧几里得算法的步骤如下:

  1. 使用普通的欧几里得算法计算 gcd(a, m)
  2. 在递归求解过程中,维护两个额外的变量 x1y1,它们满足 ax1 + my1 = gcd(a, m)
  3. 根据递归的基本情况 ax1 + my1 = gcd(a, m)mx2 + ny2 = gcd(m, n),使用迭代的方式计算 xy,使得 ax + my = gcd(a, m)
  4. 根据 x1y1 计算出 x 的值,进而求解同余方程 ax ≡ b (mod m) 的解。

拓展欧几里得算法的关键在于利用递归和迭代的方法,通过倒推的方式求解方程 ax + my = gcd(a, m),并利用这个解求解同余方程 ax ≡ b (mod m)。这个算法在密码学和编程竞赛中经常被使用,特别是在求解模逆元和解决一些与模运算相关的问题时。

人话版

拓展欧几里得算法就是可以在求解最大公约数的同时,求解出ax + by = gcd(a,b)的$(x,y)$。

注意变量名的变化,可能看着有点乱。

例如 $gcd(6,14) = 2$ 而 $2 = (-2)6 + 114$

有两个基本的应用

  1. 解不定方程$[ax + by = gcd(a,b)]$
  2. 求乘法逆元$[ ax \equiv 1 \pmod{b} ]$
    并且在求解同余方程的时候
    如果 $\text{gcd}(a, m)$ 能够整除 $b$,那么方程 $ax \equiv b \pmod{m}$ 有解,且一组解为:$x = x’ \times \frac{b}{\text{gcd}(a, m)}$

代码

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x = 1,y = 0;
return a;
}
int d = exgcd(b,a%b,y,x);
y -= a / b * x;//公式
return d;
}

代码解释

img

因此可以采取递归算法 先求出下一层的 ( x’ ) 和 ( y’ ) 再利用上述公式回代即可

例题

扩展欧几里得算法
P1082 [NOIP2012 提高组] 同余方程
线性同余方程
P2613 【模板】有理数取余
P3811 【模板】模意义下的乘法逆元


拓展欧几里得
http://pikachuxpf.github.io/posts/68bc28a9/
作者
Pikachu_fpx
发布于
2024年5月13日
许可协议