第 22 章 同余与逆元 · 知识细节练习

考点：同余的定义（A1）。

解析：$a \equiv b \pmod m$ ⇔ $m \mid (a-b)$ ⇔ $a$ 与 $b$ 除以 $m$ 的余数相同。✅ 正确

排除法：无（判断题）。混淆点：同余不是相等——$17 \equiv 5 \pmod 6$ 但 $17 \ne 5$。

关联 · 同余与余数（A6）：两种定义等价。

考点：同余的加减乘性质（A2）。

解析：同余式可以相加、相减、相乘：$a \equiv b, c \equiv d \Rightarrow a+c \equiv b+d,\ a-c \equiv b-d,\ ac \equiv bd$（模 $m$）。✅ 正确

排除法：无（判断题）。混淆点：除法不在其列（A4）——同余的运算法则到乘为止。

关联 · 模运算的除法不成立（A4）：唯一不封闭的运算。

考点：同余的传递性（A3）。

解析：同余是等价关系：自反（$a \equiv a$）、对称（$a \equiv b \Leftrightarrow b \equiv a$）、传递（$a \equiv b, b \equiv c \Rightarrow a \equiv c$）。✅ 正确

排除法：无（判断题）。混淆点：等价关系三性质常用于同余式的链式推导。

关联 · 同余的定义（A1）：等价关系的载体。

考点：模运算的除法不成立（A4）。

解析：$ac \equiv bc \pmod m$ 不能直接约去 $c$——消去律需要 $\gcd(c, m) = 1$（或同除 gcd 后调整模数）。✅ 正确

排除法：无（判断题）。混淆点：这正是"逆元"存在的意义——除不掉就乘逆元。

关联 · 同余的消去律（G6）：消去律的条件。

考点：同余方程（A5）。

解析：$ax \equiv b \pmod m$ 有解 ⇔ $\gcd(a, m) \mid b$。✅ 正确

排除法：无（判断题）。混淆点：$\gcd(a,m)=1$ 时解唯一（模 $m$）；不满足整除条件则无解。

关联 · 同余方程求解（N6）：解法的代码版。

考点：同余与余数（A6）。

解析：两种定义等价——"余数相同"是直观版本、"整除差"是运算版本。✅ 正确

排除法：无（判断题）。混淆点：C++ 的 % 给的是"余数"，同余判定就是比余数（I2）。

关联 · 同余判定（I2）：代码判定。

考点：裴蜀定理（B1）。

解析：$ax + by$ 能表示的最小正整数 = $\gcd(a, b)$，故 $ax + by = \gcd(a,b)$ 必有整数解。✅ 正确

排除法：无（判断题）。混淆点：这是 exgcd 与逆元理论的根基。

关联 · exgcd 与 gcd 的关系（B4）：exgcd 就是求这组系数。

考点：扩展欧几里得的思想（B2）。

解析：在辗转相除的回溯过程中，反推出满足 $ax + by = \gcd(a,b)$ 的系数——递归返回时修正 x、y。✅ 正确

排除法：无（判断题）。混淆点：不是枚举——是 $O(\log)$ 的确定性构造。

关联 · exgcd 的系数（B3）：修正公式。

考点：扩展欧几里得的系数（B3）。

解析：$\mathrm{exgcd}(48, 36) \to (12, 1, -1)$：$48 \times 1 + 36 \times (-1) = 12$。✅ 正确

排除法：无（判断题）。混淆点：系数不唯一（通解），但 exgcd 返回的是一组特解。

关联 · exgcd 系数输出（J2）：代码版。

考点：exgcd 与 gcd 的关系（B4）。

解析：exgcd = gcd 的扩展——返回值就是 gcd，同时多返回一对裴蜀系数。✅ 正确

排除法：无（判断题）。混淆点：辗转相除框架不变，只是回溯时多算两个系数。

关联 · 扩展欧几里得的思想（B2）：扩展点。

考点：exgcd 的通解（B5）。

解析：通解 = 特解 + 周期扰动：$x = x_0 + \frac{b}{g}t,\ y = y_0 - \frac{a}{g}t$——加一减一保持 $ax+by$ 不变。✅ 正确

排除法：无（判断题）。混淆点：符号一加一减（代入后抵消），系数除以 $g$ 后互质。

关联 · exgcd 通解验证（J6）：代码验证。

考点：exgcd 的应用（B6）。

解析：exgcd 两大应用：求逆元（$ax + my = 1$ 的 $x$）、解线性同余方程。✅ 正确

排除法：无（判断题）。混淆点：求最大值/排序/素数判定与 exgcd 无关。

关联 · exgcd 求逆元（K2）：应用代码。

考点：exgcd 过程示例（B7）。

解析：$30 \times 1 + 12 \times (-2) = 6 = \gcd(30, 12)$。✅ 正确

排除法：无（判断题）。混淆点：验证系数只要代回算一遍。

关联 · exgcd 的系数（B3）：同构题。

考点：逆元的定义（C1）。

解析：$a^{-1}$ 满足 $a \cdot a^{-1} \equiv 1 \pmod m$——模意义下的"倒数"。✅ 正确

排除法：无（判断题）。混淆点：不是 $= 0$、不是 $-a$、不是 $+$ 的逆。

关联 · 逆元计算示例（C7）：实例。

考点：逆元存在的条件（C2）。

解析：逆元存在 ⇔ $\gcd(a, m) = 1$（裴蜀定理：$ax + my = 1$ 有解）。✅ 正确

排除法：无（判断题）。混淆点：与 $a$ 是否素数无关；$a > m$ 也无妨（先取模）。

关联 · 逆元不存在的情形（H1）：反例。

考点：逆元的唯一性（C3）。

解析：模 $m$ 意义下逆元唯一——若 $ax \equiv 1$ 且 $ay \equiv 1$，则 $x \equiv y \pmod m$。✅ 正确

排除法：无（判断题）。混淆点：唯一是"模 m 同余意义下"，代表元可取任意同余值。

关联 · 逆元的定义（C1）：唯一性证明。

考点：逆元的用途（C4）。

解析：模意义下"除以 $a$" = "乘以 $a^{-1}$"——把不封闭的除法转成封闭的乘法。✅ 正确

排除法：无（判断题）。混淆点：前提 $\gcd(a, m) = 1$。

关联 · 模意义下的除法（F3）：用途的展开。

考点：逆元的运算性质（C5）。

解析：$(ab)^{-1} \equiv a^{-1} b^{-1}$——乘积的逆 = 逆的乘积（展开验证：$ab \cdot a^{-1} b^{-1} \equiv 1$）。✅ 正确

排除法：无（判断题）。混淆点：逆元与乘法可交换顺序，与加法不满足此律。

关联 · 组合数取模（G2）：多处逆元连乘的应用。

考点：0 没有逆元（C6）。

解析：$\gcd(0, m) = m \ne 1$（$m > 1$）——0 永远没有逆元，模意义下除以 0 永远非法。✅ 正确

排除法：无（判断题）。混淆点：与实数域"0 无倒数"一致。

关联 · 逆元存在的条件（C2）：条件验证。

考点：逆元计算示例（C7）。

解析：$3 \times 5 = 15 \equiv 1 \pmod 7$ → $3^{-1} \equiv 5$。✅ 正确

排除法：无（判断题）。混淆点：手算小模数逆元 = 试乘 $1 \sim m-1$。

关联 · 费马小定理求逆元（D1）：大模数的求法。

考点：费马小定理求逆元（D1）。

解析：$p$ 素数：$a^{p-1} \equiv 1$ → $a \cdot a^{p-2} \equiv 1$ → $a^{-1} \equiv a^{p-2}$（快速幂计算）。✅ 正确

排除法：无（判断题）。混淆点：指数是 $p-2$ 不是 $p-1$。

关联 · 费马小定理快速幂求逆元（K1）：代码版。

考点：扩展欧几里得求逆元（D2）。

解析：解 $ax + my = 1$（$\gcd(a,m)=1$ 有解），则 $x \bmod m$ 即 $a^{-1}$。✅ 正确

排除法：无（判断题）。混淆点：模可为合数——这是 exgcd 法对费马法的优势。

关联 · exgcd 求逆元（K2）：代码版。

考点：线性递推求逆元（D3）。

解析：$\mathrm{inv}[i] = (p - \lfloor p/i \rfloor) \cdot \mathrm{inv}[p \bmod i] \bmod p$——$O(n)$ 求全部 $1 \sim n$ 的逆元。✅ 正确

排除法：无（判断题）。混淆点：$p \bmod i < i$，故 $\mathrm{inv}[p \bmod i]$ 已算过。

关联 · 线性递推求逆元（K3）：代码版。

考点：三种方法的适用条件（D4）。

解析：费马法要素数模；exgcd 法只要互质（合数模也行）；递推法批量求 $1 \sim n$ 模素数。✅ 正确

排除法：无（判断题）。混淆点：三法的条件差异是单选题高频。

关联 · 求法选择（D6）：选择矩阵。

考点：费马小定理的条件（D5）。

解析：$p$ 素数且 $\gcd(a, p) = 1$（即 $p \nmid a$）——两个条件缺一不可。✅ 正确

排除法：无（判断题）。混淆点：合数模下费马不成立（H2/P2）。

关联 · 费马小定理（E1）：定理本体。

考点：求法选择（D6）。

解析：模 12 是合数 → 费马不适用 → exgcd 法（$\gcd(a, 12) = 1$ 时）。✅ 正确

排除法：无（判断题）。混淆点：递推法也要求素数模。

关联 · 三种方法的适用条件（D4）：条件驱动的选择。

考点：批量求逆元场景（D7）。

解析：$1 \sim n$ 全求逆元 → $O(n)$ 线性递推（每个 $O(1)$），完胜 $n$ 次快速幂的 $O(n \log p)$。✅ 正确

排除法：无（判断题）。混淆点：组合数预处理常用此批量逆元。

关联 · 批量逆元（K7）：代码版。

考点：费马小定理（E1）。

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

排除法：无（判断题）。混淆点：等价形式 $a^p \equiv a \pmod p$（对 $p \mid a$ 也成立）。

关联 · 费马小定理的条件（E2）：条件强调。

考点：费马小定理的条件（E2）。

解析：$p$ 必须素数——合数模下 $a^{p-1} \equiv 1$ 不一定成立（如 $2^{9} \not\equiv 1 \pmod{10}$）。✅ 正确

排除法：无（判断题）。混淆点：合数要用欧拉定理（指数 $\varphi(m)$）。

关联 · 欧拉定理（E4）：合数版推广。

考点：欧拉函数（E3）。

解析：$\varphi(n)$ = $1 \sim n$ 中与 $n$ 互质的个数。✅ 正确

排除法：无（判断题）。混淆点：不是素数个数（那是 $\pi(n)$）、不是约数个数。

关联 · 欧拉函数计算（M1）：代码版。

考点：欧拉定理（E4）。

解析：$\gcd(a, m) = 1$ → $a^{\varphi(m)} \equiv 1 \pmod m$——费马小定理的合数推广。✅ 正确

排除法：无（判断题）。混淆点：指数是 $\varphi(m)$ 不是 $m-1$（后者只在素数时对）。

关联 · 欧拉定理验证（M4）：代码版。

考点：费马是欧拉的特例（E5）。

解析：$p$ 素数时 $\varphi(p) = p-1$ → 欧拉定理 $a^{p-1} \equiv 1$ 即费马小定理。✅ 正确

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

关联 · 欧拉与费马（M6）：代码视角。

考点：素数模的欧拉函数（E6）。

解析：$\varphi(7) = 6$——$1 \sim 6$ 全部与 7 互质（7 是素数）。✅ 正确

排除法：无（判断题）。混淆点：素数 $p$ 的 $\varphi(p) = p-1$。

关联 · φ(p) = p - 1（M2）：代码版。

考点：模的加法乘法（F1）。

解析：加减乘都可"先各自取模再运算再取模"——$(a+b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$，乘法同理。✅ 正确

排除法：无（判断题）。混淆点：除法不在此列（乘逆元）。

关联 · 模的加法乘法（J 组 18 章 D5/D6）：入门级回顾。

考点：模意义下的减法（F2）。

解析：减法后加 $m$ 再取模——规范化到 $[0, m)$，避免负数余数。✅ 正确

排除法：无（判断题）。混淆点：C++ 的 % 对负数给出负余数（H4）。

关联 · 负数取模规范化（I5）：代码版。

考点：模意义下的除法（F3）。

解析：$\frac{a}{b} \bmod m = a \cdot b^{-1} \bmod m$（$\gcd(b,m)=1$）——除法转乘法。✅ 正确

排除法：无（判断题）。混淆点：不是整数除法、不是"各自取模再除"（H3）。

关联 · 分数取模（G3）：概念展开。

考点：大数取模技巧（F4）。

解析：连乘/连加每步取模——中间值不超过 $m^2$，避免溢出。✅ 正确

排除法：无（判断题）。混淆点：最后才取模会中途溢出（P4）。

关联 · 快速幂漏取模（P4）：错误示范。

考点：模运算与同余方程（F5）。

解析：$ax \equiv b \pmod m$ ⇔ $ax = b + km$（$k$ 整数）——同余方程即带余数的线性方程。✅ 正确

排除法：无（判断题）。混淆点：这是从同余到普通方程的翻译桥梁。

关联 · 同余方程（A5）：可解性条件。

考点：同余式化简（F6）。

解析：$\gcd(c, m) = 1$ 时可消去 $c$——消去律的条件是 $c$ 与模互质。✅ 正确

排除法：无（判断题）。混淆点：不互质则解集变大（G6 的反例）。

关联 · 同余的消去律（G6）：条件与反例。

考点：模幂（G1）。

解析：$a^b \bmod m$ 用快速幂：二进制拆指数、每步取模，$O(\log b)$。✅ 正确

排除法：无（判断题）。混淆点：先算 $a^b$ 再取模必溢出。

关联 · 快速幂取模输出（L1）：代码版。

考点：组合数取模（G2）。

解析：$C(n,k) = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \bmod p$——阶乘预处理 + 逆元。✅ 正确

排除法：无（判断题）。混淆点：$n$ 大时杨辉三角 $O(n^2)$ 空间不够，逆元法 $O(n)$ 预处理。

关联 · 组合数取模（K6）：代码版。

考点：分数取模（G3）。

解析：$\frac{a}{b} \bmod m = a \cdot b^{-1} \bmod m$——分数取模就是乘分母逆元。✅ 正确

排除法：无（判断题）。混淆点：竞赛中"输出概率/期望对 $p$ 取模"全用此式。

关联 · 分数取模（K5）：代码版。

考点：日期周期问题（G4）。

解析：$100 \equiv 2 \pmod 7$ → 星期三 + 2 = 星期五。✅ 正确

排除法：无（判断题）。混淆点：周期问题 = 取模问题——星期、时钟、循环队列皆如此。

关联 · 周期问题（N1）：代码版。

考点：密码学思想（G5）。

解析：RSA 依赖大数分解难 + 模幂/逆元易——同余逆元是公钥密码的数学地基。✅ 正确

排除法：无（判断题）。混淆点：教学定位——知道"同余有什么用"即可。

关联 · 模幂（G1）：RSA 中的模幂。

考点：同余的消去律（G6）。

解析：$2x \equiv 2 \pmod 6$ 的解是 $x \equiv 1$ 或 $4 \pmod 6$——不能消去 2（$\gcd(2,6) \ne 1$）。✅ 正确

排除法：无（判断题）。混淆点：消去律失效 = 解集分裂——这是同余与等式的关键差异。

关联 · 同余式化简（F6）：互质条件下的消去。

考点：逆元不存在的情形（H1）。

解析：$\gcd(6, 12) = 6 \ne 1$ → 6 模 12 无逆元——"除以 6"模 12 不合法。✅ 正确

排除法：无（判断题）。混淆点：存在性检查是除法取模的第一步。

关联 · 逆元存在的条件（C2）：判定依据。

考点：费马小定理误用（H2）。

解析：模 10 是合数 → 费马求逆元公式失效——必须改用 exgcd。✅ 正确

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

关联 · 费马小定理的条件（E2）：条件检查。

考点：除法取模直接除（H3）。

解析：$(10/2) \bmod 7 = 5$，但 $(10 \bmod 7)/(2 \bmod 7) = 3/2 = 1 \ne 5$——"先取模再除"是错误示范。✅ 正确

排除法：无（判断题）。混淆点：除法是唯一不能"先各自取模"的运算。

关联 · 模意义下的除法（F3）：正确做法。

考点：负数取模规范化（H4）。

解析：C++ (-7) % 3 == -1（余数符号随被除数）——数学余数 $[0, m)$ 需 ((x % m) + m) % m。✅ 正确

排除法：无（判断题）。混淆点：与 J 组 18 章 D4 呼应，S 组逆元计算里必用。

关联 · 负数取模规范化（I5）：代码版。

考点：同余综合判断（H5）。

解析：四结论全对：逆元存在 ⇔ 互质；费马求逆元要素数模；exgcd 互质恒求逆元；分数取模 = 乘分母逆元。✅ 正确

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

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

考点：取模输出（I1）。

解析：$17 \bmod 5 = 2$（$17 = 5 \times 3 + 2$）。正确答案 A。

实现要点：% 是取余运算，结果 = 被除数减去商的整数倍。手算：列竖式。

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

关联 · 同余与余数（A6）：取模即求余数。

考点：同余判定（I2）。

解析：$17 \bmod 6 = 5$、$5 \bmod 6 = 5$ → 同余 → YES。正确答案 A。

实现要点：同余判定 = 比较两数的 % m 结果。手算：分别取余。

排除法：B 是余数不等；C/D 无依据。

关联 · 同余的定义（A1）：概念题代码化。

考点：模加减输出（I3）。

解析：$(10+11) \bmod 7 = 21 \bmod 7 = 0$；$(10-11+7) \bmod 7 = 6 \bmod 7 = 6$。输出 0 6。正确答案 A。

实现要点：减法先加 $m$ 再取模——规范化到 $[0, m)$。手算：分别算和与差。

排除法：B 忘了取模；C/D 无依据。

关联 · 模意义下的减法（F2）：概念题代码化。

考点：模乘输出（I4）。

解析：$(10 \bmod 7) \times (11 \bmod 7) \bmod 7 = 3 \times 4 \bmod 7 = 12 \bmod 7 = 5$。正确答案 A。

实现要点：先各取模、乘完再取模。手算：$3 \times 4 = 12 \equiv 5$。

排除法：B 忘了最后取模；C/D 无依据。

关联 · 模的加法乘法（F1）：概念题代码化。

考点：负数取模规范化（I5）。

解析：(-7 % 3) = -1，(-1 + 3) % 3 = 2。正确答案 A。

实现要点：((x % m) + m) % m 是负数取模规范化的标准写法。手算：$-7 = 3 \times (-3) + 2$。

排除法：B 是 C++ 原始负余数；C/D 无依据。

关联 · 负数取模规范化（H4）：概念题代码化。

考点：模运算优先级（I6）。

解析：% 与 *、/ 同级，高于 +：$(7+3)\%5 = 0$；$7 + 3\%5 = 7 + 3 = 10$。输出 0 10。正确答案 A。

实现要点：% 优先级高于 +——混用必加括号。手算：按优先级拆。

排除法：B 把第一个也当 10；C/D 无依据。

关联 · 取模输出（I1）：优先级陷阱。

考点：exgcd 求 gcd 输出（J1）。

解析：exgcd 返回值 = $\gcd(48, 36) = 12$。正确答案 A。

实现要点：exgcd 与 gcd 框架相同（递归出口 $b=0$ 返回 $a$），回溯时修正系数。手算：先跑辗转相除得 gcd。

排除法：B/C 是输入；D 无依据。

关联 · exgcd 与 gcd 的关系（B4）：概念题代码化。