枣庄市网站建设_网站建设公司_UI设计师_seo优化

扩展欧几里得算法（Extended GCD）

目标：解方程

\[ax + ny = 1 \quad \text{其中 } \gcd(a, n) = 1 \]

即：求整数 \(x, y\)，使得 \(ax + ny = 1\)。
这在模运算中等价于求 \(a^{-1} \mod n\)。

---

算法描述：exgcd(a, n) → (x, y)（假设 \(a < n\)）

设：

\[n = a \cdot \left\lfloor \frac{n}{a} \right\rfloor + (n \bmod a) \]

令 \(r = n \bmod a\)，则：

\[n = aq + r, \quad q = \left\lfloor \frac{n}{a} \right\rfloor \]

我们希望解：

\[ax + ny = 1 \]

等价于：

\[(n \bmod a)x' + ay' = 1 \quad \text{即} \quad rx' + ay' = 1 \]

设 \((x', y')\) 是该方程的解，则原方程的解为：

\[\begin{cases} y = x' \\ x = y' - q \cdot x' \end{cases} \]

代入验证：

\[ax + ny = a(y' - qx') + n x' = a y' - a q x' + n x' = a y' + (n - a q) x' = a y' + r x' \]

而 \(r x' + a y' = 1\)，故成立。

---

递归终止条件

当 \(a = 0\) 时，方程变为：

\[ny = 1 \Rightarrow y = 1,\quad x = 0 \]

所以返回 \((x=0, y=1)\)。

---

算法总结（伪代码）

def exgcd(a, n):if a == 0:return (0, 1)else:q = n // ar = n % ax_prime, y_prime = exgcd(r, a)x = y_prime - q * x_primey = x_primereturn (x, y)

输出：\((x, y)\) 满足 \(ax + ny = 1\)，即 \(x \equiv a^{-1} \pmod{n}\)。

---

2. 线性时间求模逆元（适用于素数模）

设 \(p\) 为素数，对任意 \(i \in [1, p-1]\)，存在 \(i^{-1} \mod p\)。

我们可以用 递推公式 在 \(O(p)\) 时间内预处理所有逆元。

方法：利用同余关系

对任意 \(i \in [1, p-1]\)，设：

\[p = q \cdot i + r, \quad \text{其中 } q = \left\lfloor \frac{p}{i} \right\rfloor, \quad r = p \bmod i \]

则有：

\[qi + r \equiv 0 \pmod{p} \Rightarrow qi + r \equiv 0 \pmod{p} \]

两边同时乘以 \(i^{-1} r^{-1}\)：

\[q \cdot r^{-1} + i^{-1} \equiv 0 \pmod{p} \Rightarrow i^{-1} \equiv -q \cdot r^{-1} \pmod{p} \]

又因为 \(r = p \bmod i < i\)，所以 \(r^{-1} \mod p\) 已经在前面计算过。

因此可得递推式：

\[i^{-1} \equiv -\left\lfloor \frac{p}{i} \right\rfloor \cdot (p \bmod i)^{-1} \pmod{p} \]

初始值

• \(1^{-1} \equiv 1 \pmod{p}\)

算法（线性预处理）

inv = [0] * (p+1)
inv[1] = 1
for i in range(2, p):inv[i] = (- (p // i) * inv[p % i]) % p

---

3. 广义 Euler 定理（ExEuler 定理）

原始 Euler 定理

若 \(\gcd(a, n) = 1\)，则：

\[a^{\phi(n)} \equiv 1 \pmod{n} \Rightarrow a^k \equiv a^{k \bmod \phi(n)} \pmod{n} \]

但当 \(\gcd(a, n) \ne 1\) 时，此结论不成立。

---

广义 Euler 定理（适用于任意 \(a, n\)）

设 \(n = m \cdot s\)，满足：

• \(\gcd(a, m) = 1\)
• \(\gcd(m, s) = 1\)

且 \(\phi(n) = \phi(m)\phi(s)\)

则：

• \(a^{\phi(m)} \equiv 1 \pmod{m}\)
• \(a^{\phi(n)} \equiv a^{\phi(m)} \cdot a^{\phi(s)} \equiv 1 \cdot a^{\phi(s)} \pmod{m}\)

但更关键的是：当 \(s\) 中的所有质因子都出现在 \(a\) 中时，可以推出：

\[a^{\psi(s)} \equiv 0 \pmod{s} \quad \text{当 } \psi(s) \geq \log_2 n 或最高素数幂次 \]

其中 \(\psi(s)\) 是使 \(a^k \equiv 0 \pmod{s}\) 的最小正整数。

---

关键观察：指数足够大时模不变

若 \(b \geq \log_2 n\) 或 \(b \ge \phi(n)\)，则：

\[a^b \equiv a^{b \bmod \phi(n) + \phi(n)} \pmod{n} \]

为什么？

• 设 \(s = p_1^{d_1} p_2^{d_2} \cdots\)，且每个 \(p_i\) 都整除 \(a\)。

• 则 \(a^{\psi(s)} \equiv 0 \pmod{s}\)，只要 \(\psi(s) \geq \log_2 n\)。

• 此时 \(a^b \equiv 0 \pmod{s}\)，而 \(a^{b \bmod \phi(n) + \phi(n)} \equiv a^{\phi(n)} \cdot a^{b \bmod \phi(n)} \equiv 0 \pmod{s}\)。

  （这是因为一般地，有 \(\phi(n)>最高素幂次\).）

• 同时在模 \(m\) 下，由 Euler 定理：

  \[a^b \equiv a^{b \bmod \phi(n)} \pmod{m} \]

• 故整体上：

  \[a^b \equiv a^{b \bmod \phi(n) + \phi(n)} \pmod{n} \]

---

结论：广义 Euler 定理

若 \(b \geq \log_2 n\) 或 \(b \ge \phi(n)\)，则：

\[a^b \equiv a^{b \bmod \phi(n) + \phi(n)} \pmod{n} \]

✅ 特别地，当 \(a\) 与 \(n\) 不互素时，仍可用此公式快速幂模。

---

应用场景

• 快速幂计算 \(a^b \mod n\)，即使 \(\gcd(a,n) \ne 1\)
• 数论编程（如 Project Euler、密码学）
• 处理大指数下的模运算

---

\[\boxed{ \text{当 } b \geq \log_2 n \text{ 或 } b > \phi(n),\quad a^b \equiv a^{b \bmod \phi(n) + \phi(n)} \pmod{n} } \]

Euler φ 函数的性质

练习 1：证明当 \(n > 2\) 时，\(\phi(n)\) 是偶数

命题：若 \(n > 2\)，则 \(\phi(n)\) 为偶数。

---

证明思路

考虑集合：

\[\mathbb{Z}_n^* = \left\{ a \in \mathbb{Z}_n \mid \gcd(a, n) = 1 \right\} \]

其大小为 \(\phi(n)\)。我们构造一个映射：

\[\sigma: \mathbb{Z}_n^* \to \mathbb{Z}_n^*, \quad \sigma(a) = n - a \]

即：将每个与 \(n\) 互素的数 \(a\) 映射为其“补数” \(n - a\)。

---

步骤 1：\(\sigma\) 是双射

• 若 \(\gcd(a, n) = 1\)，则 \(\gcd(n - a, n) = \gcd(-a, n) = \gcd(a, n) = 1\)，所以 \(n - a \in \mathbb{Z}_n^*\)。
• \(\sigma\) 是自反的：\(\sigma(\sigma(a)) = \sigma(n - a) = n - (n - a) = a\)，即 \(\sigma^2 = \text{id}\)。
• 故 \(\sigma\) 是对合（involution），且是双射。

---

步骤 2：\(\sigma\) 将元素配对

由于 \(\sigma\) 是双射且 \(\sigma^2 = \text{id}\)，它将 \(\mathbb{Z}_n^*\) 中的元素两两配对：

\[a \leftrightarrow n - a \]

除非存在某个 \(a\) 满足 \(\sigma(a) = a\)，即：

\[n - a = a \Rightarrow n = 2a \Rightarrow a = \frac{n}{2} \]

此时要求 \(\gcd(a, n) = \gcd(n/2, n) = n/2\)，但要使 \(\gcd(a, n) = 1\)，必须有 \(n/2 = 1\)，即 \(n = 2\)。

---

步骤 3：矛盾法排除不动点

假设存在 \(a \in \mathbb{Z}_n^*\) 使得 \(\sigma(a) = a\)，即 \(n = 2a\) 且 \(\gcd(a, n) = 1\)。

则：

\[\gcd(a, 2a) = a = 1 \Rightarrow a = 1, \quad n = 2 \]

因此，只有当 \(n = 2\) 时才可能存在不动点。

---

结论

• 当 \(n > 2\) 时，\(\sigma\) 无不动点，所有元素成对出现。
• 所以 \(\phi(n)\) 是偶数。

\[\boxed{\text{当 } n > 2 \text{ 时，} \phi(n) \text{ 是偶数。}} \]

以下是将你提供的 两张手写图片内容（关于 模阶的计算与批量求逆元算法）完整、清晰地排版为 Markdown + LaTeX 代码块，并进行逻辑梳理和优化，适合用于笔记、讲义或编程参考。

---

模阶计算与批量模逆元算法

1. 求模阶：\(\text{ord}_n(a)\)

问题描述

给定整数 \(a, n\)，满足 \(\gcd(a, n) = 1\)，
求最小正整数 \(k\)，使得：

\[a^k \equiv 1 \pmod{n} \]

记作：\(\text{ord}_n(a)\)，即 \(a\) 在模 \(n\) 下的阶。

📌 性质：\(\text{ord}_n(a) \mid \phi(n)\)

---

算法思路（时间复杂度 \(O(\sqrt{n})\)）

由于 \(\text{ord}_n(a) \mid \phi(n)\)，我们可以：

1. 先计算 \(\phi(n)\)
2. 枚举 \(\phi(n)\) 的所有正因子 \(d\)
3. 按升序遍历，找到第一个满足 \(a^d \equiv 1 \pmod{n}\) 的 \(d\)

---

伪代码实现

def order(a, n):phi = euler_phi(n)  # 计算欧拉函数值divisors = get_divisors(phi)  # 获取所有正因子divisors.sort()  # 升序排列for d in divisors:if pow(a, d, n) == 1:  # 快速幂模运算return dreturn phi  # 理论上不会到达这里

✅ 时间复杂度：\(O(\sqrt{n})\)，因为因子个数不超过 \(O(\sqrt{n})\)

---

判断是否存在离散对数

问题

给定 \(a, b, n\)，且 \(\gcd(a, n) = 1\)，问是否存在整数 \(k\)，使得：

\[a^k \equiv b \pmod{n} \]

即：是否存在 \(k\) 使得 \(b\) 是 \(a\) 的幂次？

---

解法：利用阶的性质

设 \(\text{ord}_n(a) = d\)，则生成子群：

\[\langle a \rangle = \{1, a, a^2, \dots, a^{d-1}\} \subseteq \mathbb{Z}_n^* \]

若存在 \(k\) 使得 \(a^k \equiv b \pmod{n}\)，则 \(b \in \langle a \rangle\)，故：

\[|b| \mid d \Rightarrow b^d \equiv 1 \pmod{n} \]

🔹 必要条件：\(b^d \equiv 1 \pmod{n}\)

此时需要使用BSGS算法判定并求解。

---

特殊情况：当 \(\mathbb{Z}_n^*\) 是循环群时（即 \(n\) 有原根）

若 \(\mathbb{Z}_n^*\) 是循环群，则它有唯一的有限阶子群对应每个因数。

因此，充要条件变为：

\[b^d \equiv 1 \pmod{n} \]

✅ 即：在循环群中，\(b \in \langle a \rangle\) 当且仅当 \(b^{\text{ord}_n(a)} \equiv 1 \pmod{n}\)

---

2. 批量求模逆元（高效算法）

问题描述

给定素数 \(p\) 和数组 \(a_1, a_2, \dots, a_n\)，满足：

• \(n \leq 10^5\)
• \(1 \leq a_i < p\)

目标：计算所有 \(a_i^{-1} \mod p\)，即每个 \(a_i\) 在模 \(p\) 下的乘法逆元。

---

优秀做法：前缀积 + 逆推（时间复杂度 \(O(n + \log p)\)）

核心思想

1. 计算前缀积：

   \[P_k = \prod_{i=1}^k a_i \mod p \]

2. 计算总积的逆元：

   \[P_n^{-1} \mod p \]

3. 从后往前递推求每个 \(a_i^{-1}\)：

   • 利用恒等式：
     \[a_i^{-1} \equiv P_{i-1} \cdot P_n^{-1} \mod p \]

---

伪代码实现

def getInv(a, p):n = len(a)prefix = [1] * (n + 1)  # 前缀积数组# 步骤1：计算前缀积for i in range(n):prefix[i + 1] = (prefix[i] * a[i]) % p# 步骤2：计算总积的逆元（Fermat 小定理）invAll = pow(prefix[n], p - 2, p)# 步骤3：从后往前递推求逆元inv = [0] * nfor i in range(n - 1, -1, -1):inv[i] = (invAll * prefix[i]) % pinvAll = (invAll * a[i]) % p  # 更新为下一个的总积逆元return inv

---

算法详解

变量	含义
prefix[i]	\(\prod_{j=1}^{i-1} a_j \mod p\)
invAll	当前剩余部分的乘积的逆元
inv[i]	\(a_i^{-1} \mod p\)

---

时间复杂度分析

• 前缀积：\(O(n)\)
• 快速幂求逆：\(O(\log p)\)
• 逆向递推：\(O(n)\)

总时间复杂度：\(\boxed{O(n + \log p)}\)

---

课后习题：群论与数论基础

① 易题：交换律与幂运算

题目：设 \(a, b \in G\)，证明：

\[(ab)^n = a^n b^n \quad \text{当且仅当} \quad ab = ba \]

证明

• \((\Rightarrow)\)：显然，当 \(n=1\) 时成立。

• \((\Leftarrow)\)：假设 \(ab = ba\)，用数学归纳法证明：

  • 基础情况：\(n=1\)，\((ab)^1 = ab = a^1 b^1\)

  • 归纳步：假设 \((ab)^k = a^k b^k\)，则

    \[(ab)^{k+1} = (ab)^k (ab) = a^k b^k ab = a^k a b^k b = a^{k+1} b^{k+1} \]

    故成立。

因此，\((ab)^n = a^n b^n\) 当且仅当 \(ab = ba\)。

---

② 中等题：Wilson 定理

题目：设 \(p\) 为奇素数，证明：

\[(p-1)! \equiv -1 \pmod{p} \]

（即 Wilson 定理）

证明

注意到 \(1, 2, \dots, p-1\) 恰好是 \(\mathbb{Z}_p^*\) 的全部元素。

对任意 \(i \in \mathbb{Z}_p^*\)，存在唯一逆元 \(i^{-1} \in \mathbb{Z}_p^*\)，满足：

\[i \cdot i^{-1} \equiv 1 \pmod{p} \]

考虑何时 \(i^{-1} = i\)，即：

\[i^2 \equiv 1 \pmod{p} \Rightarrow (i-1)(i+1) \equiv 0 \pmod{p} \Rightarrow i \equiv \pm 1 \pmod{p} \]

所以只有 \(i = 1\) 和 \(i = p-1\) 是自身的逆元。

其余元素两两配对：\(i\) 与 \(i^{-1}\) 不同，乘积为 1。

因此：

\[(p-1)! = 1 \cdot 2 \cdot \cdots \cdot (p-2) \cdot (p-1) = \left( \prod_{\substack{i=2 \\ i \ne p-1}}^{p-2} i \cdot i^{-1} \right) \cdot 1 \cdot (p-1) \equiv 1 \cdot (p-1) \equiv -1 \pmod{p} \]

得证：\((p-1)! \equiv -1 \pmod{p}\)

---

③ 中等题：有限群的幂映射是双射

题目：设 \(|G| = n\)，且 \(\gcd(k, n) = 1\)，定义映射：

\[\phi: G \to G,\quad \phi(a) = a^k \]

证明：\(\phi\) 是双射。

证明

第一步：证明 \(\phi\) 是单射

设 \(\phi(a) = \phi(b)\)，即 \(a^k = b^k\)

由于 \(\gcd(k, n) = 1\)，存在整数 \(u, v\) 使得：

\[uk + vn = 1 \]

则：

\[a^k = b^k \Rightarrow a^{uk} = b^{uk} \Rightarrow (a^{uk}) = (b^{uk}) \Rightarrow a^{1 - vn} = b^{1 - vn} \Rightarrow a \cdot a^{-vn} = b \cdot b^{-vn} \Rightarrow a = b \quad (\text{因为 } a^n = b^n = e) \]

故 \(\phi\) 是单射。

第二步：有限集上的单射必是双射

由于 \(G\) 是有限集合，单射自动是满射，因此 \(\phi\) 是双射。

得证。

---

④ 易题：Euler 判定（平方剩余）

题目：设 \(p\) 为奇素数，且 \(p \nmid a\)，证明：

\[a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p} \]

证明

由 Fermat 小定理：

\[a^{p-1} \equiv 1 \pmod{p} \Rightarrow \left(a^{\frac{p-1}{2}}\right)^2 \equiv 1 \pmod{p} \Rightarrow a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p} \]

得证。

---

⑤ 中等题：\(\mathbb{Z}_{2^k}^*\) 不是循环群（\(k \geq 3\)）

题目：证明：当 \(n = 2^k\) 且 \(k \geq 3\) 时，\(\mathbb{Z}_n^*\) 不是循环群。

方法一：阶分析法

已知 \(\phi(n) = 2^{k-1}\)，若 \(\mathbb{Z}_n^*\) 是循环群，则存在原根 \(g\)，其阶为 \(2^{k-1}\)。

但可证：对任意 \(a \in \mathbb{Z}_n^*\)，有：

\[a^{2^{k-2}} \equiv 1 \pmod{2^k} \]

证明（归纳法）：

• 基础：\(k=3\)，\(n=8\)，\(\mathbb{Z}_8^* = \{1,3,5,7\}\)，验证每个元素的平方模 8 都是 1。
• 归纳假设：设 \(a^{2^{k-3}} \equiv 1 \pmod{2^{k-1}}\)，则 \(a = 1 + q \cdot 2^{k-1}\)

则：

\[a^2 = (1 + q \cdot 2^{k-1})^2 = 1 + 2q \cdot 2^{k-1} + q^2 \cdot 2^{2k-2} = 1 + q \cdot 2^k + \cdots \equiv 1 \pmod{2^k} \]

故 \(a^{2^{k-2}} \equiv 1 \pmod{2^k}\)

但循环群中应存在阶为 \(2^{k-1}\) 的元素，矛盾。

所以 \(\mathbb{Z}_{2^k}^*\) 不是循环群（\(k \geq 3\)）

---

方法二：反证法 + 方程根个数

若 \(\mathbb{Z}_n^*\) 是循环群，则方程：

\[x^2 \equiv 1 \pmod{n} \]

最多有两个解。

但实际上：

• \(x = 1\) 是解

• \(x = -1\) 是解

• 取 \(x = 2^{k-1} + 1\)，则：

  \[x^2 = (2^{k-1} + 1)^2 = 2^k + 2^{2k-2} + 1 \equiv 1 \pmod{2^k} \]

所以至少有三个解：\(1, -1, 2^{k-1}+1\)

矛盾！

故 \(\mathbb{Z}_{2^k}^*\) 不是循环群。

第二档课后习题

① 易

\(n\) 个正整数 \(a_1, \dots, a_n\)，素数 \(p\)。计算 \((\forall i)\)：

\[\left( \prod_{j \neq i} a_j \right)^{-1} \pmod p \]

设计 \(O(n)\) 算法：
只需计算 \(prod = \prod a_i\)，则：

\[\left( \prod_{i \neq j} a_j \right)^{-1} = (prod^{-1} \times a_j) \pmod p \]

---

2 中难

证明： \(\forall n \in \mathbb{Z}^+\)，\(\exists n\) 个连续正整数，它们中没有素数幂。

证明过程：
我们任取 \(2n\) 个不同的素数 \(p_1, p_2, \dots, p_{2n-1}, p_{2n}\)。
并令：

\[\begin{cases} A + 1 \equiv 0 \pmod{p_1 p_2} \\ A + 2 \equiv 0 \pmod{p_3 p_4} \\ \vdots \\ A + n \equiv 0 \pmod{p_{2n-1} p_{2n}} \end{cases} \implies \text{模数两两互质}\]

由 CRT（中国剩余定理）知，存在 \(A \in \mathbb{N}^*\) s.t. 同时满足上述方程组。则对于每一个 \(A+k\)（\(1 \le k \le n\)），它至少有两个不同的素因子，因此不可能是素数幂。 \(\Box\)