拓展欧几里得
前置知识
最大公约数
GCD与LCM模运算
模运算的基本规则与四则运算基本一致:
为什么没有除法,是因为除法在这里比较特别。
同余
概念
如果 $a$ 和 $b$ 除以 $c$ 的余数相同,就说 $a$ 和 $b$ 关于模 $c$ 同余,记作 $a \equiv b \pmod{c}$。 > 如果 $a$ 和 $b$ 的差能够被 $m$ 整除,那么就说 $a$ 和 $b$ 关于 $m$ 同余。
同余关系是一种等价关系
- 自反性:一个数永远和本身同余
- 对称性:$a$ 和 $b$ 同余,$b$ 和 $a$ 也同余
- 传递性:$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}$ 有解,否则无解。
解法:
- 使用拓展欧几里得算法找到整数 $x’$ 和 $y’$,使得 $ax’ + my’ = \text{gcd}(a, m)$。
- 如果 $\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}$。
应用
费马小定理在密码学、编程竞赛中的算法设计等领域有着重要应用。
模幂运算: 费马小定理提供了一种快速计算模幂的方法。在计算 $a^b \pmod{p}$ 时,可以先使用费马小定理将指数化简,然后再进行模幂运算,大大提高了计算效率。
模反元素: 如果需要求解模方程 $ax \equiv 1 \pmod{p}$,即求解关于 $x$ 的同余方程的解,其中 $p$ 是素数,那么根据费马小定理,$x \equiv a^{p-2} \pmod{p}$ 就是方程的解。这提供了一种高效的方法来求解模反元素。
素性检测: 费马小定理可以作为素性检测算法的一部分。在 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)
的整数解 x
和 y
,还可以根据这个解得到同余方程 ax ≡ b (mod m)
的解。
拓展欧几里得算法的步骤如下:
- 使用普通的欧几里得算法计算
gcd(a, m)
。 - 在递归求解过程中,维护两个额外的变量
x1
和y1
,它们满足ax1 + my1 = gcd(a, m)
。 - 根据递归的基本情况
ax1 + my1 = gcd(a, m)
和mx2 + ny2 = gcd(m, n)
,使用迭代的方式计算x
和y
,使得ax + my = gcd(a, m)
。 - 根据
x1
和y1
计算出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$
有两个基本的应用
- 解不定方程$[ax + by = gcd(a,b)]$
- 求乘法逆元$[ 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 |
|
代码解释
因此可以采取递归算法 先求出下一层的 ( x’ ) 和 ( y’ ) 再利用上述公式回代即可
例题
扩展欧几里得算法
P1082 [NOIP2012 提高组] 同余方程
线性同余方程
P2613 【模板】有理数取余
P3811 【模板】模意义下的乘法逆元