第 23 章 费马欧拉威尔逊 · 知识细节练习

考点：费马小定理回顾（A1）。

解析：$p$ 素数、$p \nmid a$ → $a^{p-1} \equiv 1 \pmod p$。✅ 正确

排除法：无（判断题）。混淆点：条件两条——素数模 + 不整除。

关联 · 费马的等价形式（A2）：另一形态。

考点：费马的等价形式（A2）。

解析：$a^p \equiv a \pmod p$ 对所有整数 $a$ 成立（$p \mid a$ 时两边都是 0）——是 $a^{p-1} \equiv 1$ 的推广形态。✅ 正确

排除法：无（判断题）。混淆点：等价形式放宽了 $\gcd$ 条件。

关联 · a^p mod p 输出（I3）：代码验证。

考点：费马的应用（A3）。

解析：两大应用——求模素数的逆元（$a^{p-2}$）与指数降幂（指数对 $p-1$ 取模）。✅ 正确

排除法：无（判断题）。混淆点：求最大值/排序/图遍历与费马无关。

关联 · 费马求逆元（I2）：应用代码。

考点：费马的逆命题（A4）。

解析：逆命题不成立——合数 $n$ 也可能满足 $a^{n-1} \equiv 1$（伪素数），"费马条件 ⇒ 素数"是错误推理。✅ 正确

排除法：无（判断题）。混淆点：这是费马测试的软肋（E3/H1）。

关联 · 伪素数（A5）：反例实体。

考点：伪素数（A5）。

解析：伪素数 = 满足某基 $a$ 的费马条件的合数（341 对基 2：$2^{340} \equiv 1$）。✅ 正确

排除法：无（判断题）。混淆点：伪素数是合数，不是素数。

关联 · 伪素数 341（M3）：代码实证。

考点：卡迈克尔数（A6）。

解析：卡迈克尔数（561 等）= 对所有互质基都满足费马条件的合数——费马测试对其完全失效。✅ 正确

排除法：无（判断题）。混淆点：比普通伪素数更"顽固"。

关联 · Miller-Rabin 思想（E4）：卡迈克尔数的克星。

考点：欧拉函数公式（B1）。

解析：$\varphi(n) = n \prod_{p \mid n}(1 - \frac{1}{p})$——对每个不同质因子打折。✅ 正确

排除法：无（判断题）。混淆点：$n-1$ 只在 $n$ 为素数时正确。

关联 · φ 公式输出（J1）：代码版。

考点：欧拉函数的积性（B2）。

解析：$\gcd(m,n) = 1$ 时 $\varphi(mn) = \varphi(m)\varphi(n)$——积性函数。✅ 正确

排除法：无（判断题）。混淆点：不互质时不成立（$\varphi(4) = 2$ 但 $\varphi(2)^2 = 1$）。

关联 · φ 积性验证（J2）：代码版。

考点：φ(p^k)（B3）。

解析：$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$——$1 \sim p^k$ 中每 $p$ 个数有 1 个被 $p$ 整除。✅ 正确

排除法：无（判断题）。混淆点：$p^k - 1$ 是错误直觉（含与 $p$ 不互质的数）。

关联 · 欧拉函数公式（B1）：特例。

考点：φ 的计算（B4）。

解析：$\varphi(100) = 100 \times \frac{1}{2} \times \frac{4}{5} = 40$。✅ 正确

排除法：无（判断题）。混淆点：$100$ 的质因子是 2 和 5，各打折一次。

关联 · φ 公式输出（J1）：同数值代码题。

考点：欧拉降幂（B5）。

解析：互质时 $a^b \equiv a^{b \bmod \varphi(m)} \pmod m$——指数可对 $\varphi(m)$ 取模。✅ 正确

排除法：无（判断题）。混淆点：注意"取模为 0 时指数取 $\varphi(m)$"的细节（L4）。

关联 · 降幂计算（J4）：代码版。

考点：欧拉定理的应用（B6）。

解析：欧拉定理用于合数模的指数降幂——费马只覆盖素数模。✅ 正确

排除法：无（判断题）。混淆点：欧拉定理不能完全判定素数（那是威尔逊/测试的事）。

关联 · 欧拉降幂（B5）：降幂即应用。

考点：欧拉函数示例（B7）。

解析：$\varphi(9) = 9 \times \frac{2}{3} = 6$（1、2、4、5、7、8）。✅ 正确

排除法：无（判断题）。混淆点：9 是 $3^2$，公式给 $9 - 3 = 6$。

关联 · φ(p^k)（B3）：k=2 实例。

考点：威尔逊定理陈述（C1）。

解析：$p$ 素数 ⇔ $(p-1)! \equiv -1 \pmod p$——阶乘与素性的充要关系。✅ 正确

排除法：无（判断题）。混淆点：是 $(p-1)!$ 不是 $p!$（$p! \equiv 0$）。

关联 · 威尔逊的逆命题（C2）：双向性。

考点：威尔逊的逆命题（C2）。

解析：逆命题成立——$(n-1)! \equiv -1 \pmod n$ 则 $n$ 素数（否则 $n$ 的因子会出现在阶乘中）。✅ 正确

排除法：无（判断题）。混淆点：与费马形成对比——费马逆命题不成立。

关联 · 威尔逊与费马对比（C6）：强弱对比。

考点：威尔逊判定素数（C3）。

解析：威尔逊给出充要条件判定——理论完备，但阶乘计算代价巨大。✅ 正确

排除法：无（判断题）。混淆点：理论强 ≠ 实用强。

关联 · 威尔逊的局限（C5）：代价分析。

考点：威尔逊的应用（C4）。

解析：应用 = 计算 $(p-1)! \bmod p$、化简含阶乘的同余式（如 20! mod 23）。✅ 正确

排除法：无（判断题）。混淆点：快速排序/gcd/最短路与威尔逊无关。

关联 · 阶乘模应用（K7）：应用代码。

考点：威尔逊的局限（C5）。

解析：$(n-1)!$ 随 $n$ 爆炸增长——只用于理论推导与小规模手算，不用于实际判定。✅ 正确

排除法：无（判断题）。混淆点：工程判定用 Miller-Rabin。

关联 · 判定方法选择（D7）：工程选择。

考点：威尔逊与费马对比（C6）。

解析：威尔逊是充要（双向），费马是必要（单向）——威尔逊理论更强但计算更贵。✅ 正确

排除法：无（判断题）。混淆点：强与贵的权衡是数论判定的经典主题。

关联 · 三大定理总表（D1）：总表。

考点：威尔逊真题计算（C7）。

解析：$10! \equiv -1 \equiv 10 \pmod{11}$。✅ 正确

排除法：无（判断题）。混淆点：$(p-1)! \equiv p-1 \pmod p$（即 $-1$ 的代表元）。

关联 · (p-1)! mod p（K2）：代码版。

考点：三大定理总表（D1）。

解析：费马（素数模、$a^{p-1} \equiv 1$）、欧拉（互质、$a^{\varphi(m)} \equiv 1$）、威尔逊（充要、$(p-1)! \equiv -1$）——三者的精确陈述。✅ 正确

排除法：无（判断题）。混淆点：条件与结论的精确对应，S 组单选高频。

关联 · 条件对比（D2）：条件矩阵。

考点：条件对比（D2）。

解析：费马要素数模；欧拉只要求互质（模可合数）；威尔逊是充要条件——适用范围欧拉最广、判定力威尔逊最强。✅ 正确

排除法：无（判断题）。混淆点："条件强度"与"判定强度"是两个维度。

关联 · 三大定理总表（D1）：总表对照。

考点：应用场景（D3）。

解析：模 10 是合数 → 降幂用欧拉定理（费马不适用）。✅ 正确

排除法：无（判断题）。混淆点：模合数 + 费马 = 经典错误。

关联 · 欧拉定理的应用（B6）：合数模降幂。

考点：降幂链（D4）。

解析：降幂链 = 费马（素数模）→ 欧拉（互质合数模）→ 广义欧拉（不互质，指数 $b \bmod \varphi(m) + \varphi(m)$）——适用范围递增。✅ 正确

排除法：无（判断题）。混淆点：广义形式是"指数加 φ(m)"的补偿。

关联 · 欧拉降幂公式（F3）：广义形式。

考点：定理互推（D5）。

解析：$m$ 素数时 $\varphi(m) = m-1$ → 欧拉定理退化为费马小定理。✅ 正确

排除法：无（判断题）。混淆点：特例关系——费马 ⊂ 欧拉。

关联 · 费马是欧拉的特例（J 组 22 章 E5）：衔接。

考点：真题综合（D6）。

解析：恒真命题 = 威尔逊方向（$p$ 素数 ⇒ $(p-1)! \equiv -1$）；B 是威尔逊逆命题的否定形式（错）；C 是费马逆命题（错）；D 无依据。✅ 正确

排除法：无（判断题）。混淆点：辨析"哪个方向恒真"是真题套路。

关联 · 威尔逊定理陈述（C1）：方向性。

考点：判定方法选择（D7）。

解析：工程判定大整数素数 = Miller-Rabin（多轮随机基）——快且误判率极低。✅ 正确

排除法：无（判断题）。混淆点：威尔逊算不动、费马被伪素数骗、试除太慢。

关联 · Miller-Rabin 思想（E4）：工程解。

考点：试除法回顾（E1）。

解析：试除 $2 \sim \sqrt{n}$ → $O(\sqrt{n})$。✅ 正确

排除法：无（判断题）。混淆点：试除到 $n$ 是 $O(n)$（错误写法）。

关联 · 试除输出（M1）：代码版。

考点：费马素性测试（E2）。

解析：随机基 $a$ 检查 $a^{n-1} \equiv 1$——不满足必合数；满足"可能素数"。✅ 正确

排除法：无（判断题）。混淆点：单向可靠——判合数可靠、判素数不可靠。

关联 · 费马测试代码（I5）：代码版。

考点：伪素数反例（E3）。

解析：$341 = 11 \times 31$ 且 $2^{340} \equiv 1 \pmod{341}$——费马测试被骗。✅ 正确

排除法：无（判断题）。混淆点：341 是最小的基 2 伪素数，经典反例。

关联 · 伪素数（A5）：概念题代码化。

考点：Miller-Rabin 思想（E4）。

解析：费马检查 + 二次探测（检查 $x^2 \equiv 1$ 的非平凡根）+ 多轮随机基。✅ 正确

排除法：无（判断题）。混淆点：二次探测是识破伪素数的关键增量。

关联 · 概率判定概念（E6）：概率语义。

考点：确定性判定（E5）。

解析：试除与威尔逊是确定性判定；费马/Miller-Rabin 是概率判定（极小概率误判）。✅ 正确

排除法：无（判断题）。混淆点：概率判定结果本身是确定的，只是"可能错"。

关联 · 判定方法选择（D7）：选择矩阵。

考点：概率判定概念（E6）。

解析："概率"指误判概率（Miller-Rabin 每轮 ≤ 1/4，多轮趋零）——不是结果随机。✅ 正确

排除法：无（判断题）。混淆点：k 轮后误判 ≤ $4^{-k}$，工程上 20 轮即可放心。

关联 · Miller-Rabin 思想（E4）：误判率来源。

考点：快速幂回顾（F1）。

解析：二进制拆分指数——位为 1 乘入、底数平方，$O(\log n)$。✅ 正确

排除法：无（判断题）。混淆点：连乘是 $O(n)$。

关联 · 快速幂填空（O5）：代码版。

考点：指数循环节（F2）。

解析：互质时 $a^k \bmod m$ 呈周期、周期整除 $\varphi(m)$——降幂的根基。✅ 正确

排除法：无（判断题）。混淆点：周期（阶）是 $\varphi(m)$ 的因子（G3）。

关联 · 循环节输出（L2）：代码版。

考点：欧拉降幂公式（F3）。

解析：广义欧拉降幂：$a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod m$（$b \ge \varphi(m)$）——不要求互质。✅ 正确

排除法：无（判断题）。混淆点：指数加 $\varphi(m)$ 是对不互质情形的补偿。

关联 · 降幂链（D4）：广义一环。

考点：降幂实例（F4）。

解析：$\varphi(10) = 4$，$1000 \bmod 4 = 0$（取指数 4）→ $3^4 = 81 \equiv 1$。✅ 正确

排除法：无（判断题）。混淆点：指数取模为 0 时取 $\varphi(m)$ 本身，不是 0。

关联 · 降幂计算（J4）：代码版。

考点：大指数处理（F5）。

解析：指数塔级大数 → 欧拉降幂递归：指数对 $\varphi(m)$ 取模，$\varphi$ 逐层缩小到 1。✅ 正确

排除法：无（判断题）。混淆点：直接算 $a^b$ 必溢出。

关联 · 大指数降幂（L1）：代码版。

考点：模幂应用（F6）。

解析：RSA 的 $m^e \bmod n$ 与 $c^d \bmod n$ 都靠快速幂——模幂是密码学核心运算。✅ 正确

排除法：无（判断题）。混淆点：效率来自快速幂 $O(\log e)$。

关联 · 密码学演示（N6）：迷你 RSA。

考点：gcd 相关回顾（G1）。

解析：$\gcd(a,m) = 1$ 是逆元存在、欧拉定理可用的共同前提。✅ 正确

排除法：无（判断题）。混淆点：互质是模运算的"入场券"。

关联 · 逆元存在的条件（J 组 22 章 C2）：衔接。

考点：互质与欧拉（G2）。

解析：$\varphi(n)$ 统计的正是与 $n$ 互质的数的个数。✅ 正确

排除法：无（判断题）。混淆点：欧拉函数 = 互质计数函数。

关联 · 互质统计（N1）：代码版。

考点：阶与循环（G3）。

解析：最小 $k$ 使 $a^k \equiv 1$ 称为 $a$ 的阶，且 $k \mid \varphi(m)$。✅ 正确

排除法：无（判断题）。混淆点：阶是 $\varphi(m)$ 的因子——循环节长度的理论依据。

关联 · 指数循环节（F2）：阶与周期。

考点：原根概念（G4）。

解析：阶恰等于 $\varphi(m)$ 的元素 $g$ 为原根——$g$ 的幂遍历所有与 $m$ 互质的剩余类。✅ 正确

排除法：无（判断题）。混淆点：原根存在性依赖 $m$ 的结构（如素数必有原根）。

关联 · 离散对数思想（G5）：原根的用途。

考点：离散对数思想（G5）。

解析：已知 $g, y$ 求 $x$（$g^x \equiv y$）计算困难——Diffie-Hellman 的安全基础。✅ 正确

排除法：无（判断题）。混淆点：普通对数是容易的，模意义下是困难的。

关联 · 数论在密码学（G6）：三大支柱之一。

考点：数论在密码学（G6）。

解析：RSA（模幂+逆元）、Diffie-Hellman（离散对数）、素性测试——密码学三大支柱都在数论上。✅ 正确

排除法：无（判断题）。混淆点：教学定位——知道数论"为什么重要"。

关联 · 密码学演示（N6）：迷你演示。

考点：费马逆命题误判（H1）。

解析：341 满足 $2^{340} \equiv 1$ 但它是合数——"费马条件 ⇒ 素数"错误。✅ 正确

排除法：无（判断题）。混淆点：单向推理的纪律。

关联 · 伪素数反例（E3）：同例双题。

考点：威尔逊方向（H2）。

解析：$p$ 素数 ⇔ $(p-1)! \equiv -1$——两个方向都成立，别只记一半。✅ 正确

排除法：无（判断题）。混淆点：与费马的单向性形成对照。

关联 · 威尔逊的逆命题（C2）：方向性。

考点：欧拉函数计算错（H3）。

解析：$\varphi(12) = 4$ 不是 11——统计互质个数而非 $n-1$。✅ 正确

排除法：无（判断题）。混淆点：$n-1$ 只在 $n$ 素数时成立。

关联 · φ 公式错（P4）：代码错误版。

考点：降幂条件（H4）。

解析：互质降幂要求 $\gcd(a,m) = 1$；不互质必须用广义降幂（指数加 $\varphi(m)$）。✅ 正确

排除法：无（判断题）。混淆点：条件检查是降幂第一步（P3）。

关联 · 降幂条件错（P3）：错误示范。

考点：综合判断（H5）。

解析：四结论全对：费马要素数模且逆命题不成立；欧拉对互质恒成立；威尔逊充要；伪素数骗费马、骗不过 Miller-Rabin。✅ 正确

排除法：无（判断题）。混淆点：本章核心结论收官自查。

关联 · 本章全部核心结论：收官综合判断题。

考点：费马验证输出（I1）。

解析：$2^6 = 64 \equiv 1 \pmod 7$——费马小定理验证。正确答案 A。

实现要点：快速幂算 $a^{p-1} \bmod p$，素数模下应为 1。手算：$64 \bmod 7$。

排除法：B 是底数；C 是 -1；D 无依据。

关联 · 费马小定理回顾（A1）：概念题代码化。

考点：费马求逆元（I2）。

解析：$4^5 \bmod 7$：$4^2 = 16 \equiv 2$、$4^4 \equiv 4$、$4^5 \equiv 2$——4 的逆元是 2。正确答案 A。

实现要点：费马求逆元 = 快速幂 $a^{p-2}$。手算：验证 $4 \times 2 = 8 \equiv 1$。

排除法：B 是底数；C 是 1；D 无依据。

关联 · 费马求逆元（J 组 22 章 D1）：衔接。

考点：a^p mod p 输出（I3）。

解析：$5^7 = 5^6 \times 5 \equiv 5 \pmod 7$——等价形式 $a^p \equiv a$。正确答案 A。

实现要点：$a^p \bmod p = a \bmod p$（对任意 $a$）。手算：费马 $5^6 \equiv 1$。

排除法：B 是 1（$a^{p-1}$）；C/D 无依据。

关联 · 费马的等价形式（A2）：概念题代码化。

考点：伪素数检测（I4）。

解析：$2^{340} \equiv 1 \pmod{341}$——341 是基 2 伪素数（$341 = 11 \times 31$）。正确答案 A。

实现要点：伪素数检测 = 合数 + 费马条件成立。手算：程序验证 $2^{340} \bmod 341 = 1$。

排除法：B/C/D 无依据。

关联 · 伪素数反例（E3）：概念题代码化。

考点：费马测试代码（I5）。

解析：$2^{14} \bmod 15$：$2^4 = 16 \equiv 1$ → $2^{14} = 2^{12} \times 4 \equiv 4 \ne 1$ → COMPOSITE。正确答案 A。

实现要点：费马测试 = 检查 $a^{n-1} \bmod n$ 是否为 1；不为 1 必合数。手算：利用 $2^4 \equiv 1$ 化简。

排除法：B 是"可能素数"；C/D 无依据。

关联 · 费马素性测试（E2）：概念题代码化。

考点：费马降幂（I6）。

解析：$100 \bmod 6 = 4$ → $2^4 = 16 \equiv 2 \pmod 7$。正确答案 A。

实现要点：费马降幂 = 指数对 $p-1$ 取模。手算：$16 \bmod 7 = 2$。

排除法：B 是 $2^2$；C 是 $2^3$；D 无依据。

关联 · 费马的应用（A3）：降幂代码。

考点：φ 公式输出（J1）。

解析：$\varphi(100) = 100 \times \frac{1}{2} \times \frac{4}{5} = 40$。正确答案 A。

实现要点：φ 公式 = 对每个不同质因子 r = r / i * (i - 1)。手算：质因子 2、5。

排除法：B 是 n-1；C 是 n/2；D 无依据。

关联 · 欧拉函数公式（B1）：概念题代码化。

考点：φ 积性验证（J2）。

解析：$\varphi(3) = 2$、$\varphi(5) = 4$、$\varphi(15) = 8 = 2 \times 4$。输出 2 4 8。正确答案 A。

实现要点：互质积性 $\varphi(mn) = \varphi(m)\varphi(n)$。手算：逐个统计互质数。

排除法：B/C/D 无依据。

关联 · 欧拉函数的积性（B2）：概念题代码化。

考点：欧拉定理验证（J3）。

解析：$3^4 = 81 \equiv 1 \pmod{10}$——欧拉定理 $\varphi(10) = 4$。正确答案 A。

实现要点：欧拉定理验证 = $a^{\varphi(m)} \bmod m$ 应为 1。手算：$81 \bmod 10$。

排除法：B/C/D 无依据。

关联 · 欧拉定理（J 组 22 章 E4）：衔接。

考点：降幂计算（J4）。

解析：$1000 \bmod 4 = 0$，代码输出 $3^0 = 1$——与正确值 $3^4 \equiv 1$ 一致（$3^4 \equiv 1$）。正确答案 A。

实现要点：互质降幂 = 指数对 $\varphi(m)$ 取模；取模为 0 时指数取 $\varphi(m)$（本题碰巧 $3^0 = 3^4 = 1$）。手算：$3^4 = 81 \equiv 1$。

排除法：B/C/D 无依据。

关联 · 欧拉降幂（B5）：概念题代码化。

考点：φ 批量（J5）。

解析：筛法 φ(1..12) = 1 1 2 2 4 2 6 4 6 4 10 4。正确答案 A。

实现要点：欧拉筛法 = 每个素数给其倍数打折 phi[j] = phi[j] / i * (i - 1)。手算：按素数 2、3、5、7、11 逐轮打折。

排除法：B 是原值；C/D 无依据。

关联 · φ 公式输出（J1）：批量版。