数论期末复习
适用范围：柯召、孙琦《数论讲义（上册，第二版）》第 1-6 章。本文按教材目录整理，目标是期末复习：先把概念、定理和方法串起来，再配合典型例题训练计算与证明。
复习时建议按下面顺序推进：
- 先背熟每章的定义、定理条件和结论。
- 再掌握证明思路，尤其是“为什么能用这个工具”。
- 最后做例题，把同余、反演、二次互反律、原根和素性判别这些计算型内容练熟。
目录总览
- 第一章 整数的唯一分解定理
- §1 整除性
- §2 最大公因数与辗转相除法
- §3 最小公倍数
- §4 素数、整数的唯一分解定理
- §5 厄拉多塞筛法
- §6 麦什涅数、费马数
- §7 完全数
- §8 一次不定方程
- §9 抽屉原理
- 第二章 同余式
- §1 同余的定义和基本性质
- §2 剩余类和完全剩余系
- §3 缩系
- §4 一次同余式
- §5 模数是素数的同余式
- §6 孙子剩余定理及其应用举例
- §7 模数是素数幂的同余式
- §8 整数的剩余表示
- §9 逐步淘汰原则
- §10 Wolstenholme 定理的推广
- §11 覆盖同余式组
- 第三章 数论函数
- §1 数论函数 $\mathrm{pot}_p n$
- §2 麦比乌斯函数 $\mu(n)$
- §3 欧拉函数 $\varphi(n)$
- §4 数论函数的狄利克雷乘积
- §5 麦比乌斯反演公式
- §6 积性函数
- §7 数论函数 $\pi(n)$
- §8 卢卡斯序列
- §9 陷门单向函数与公开密钥码
- 第四章 二次剩余
- §1 二次剩余
- §2 勒让德符号
- §3 高斯引理
- §4 二次互反律
- §5 二次剩余理论应用举例
- §6 二次同余式的解法和解数
- §7 雅可比符号
- §8 表素数为平方和
- §9 表正整数为平方和
- 第五章 原根
- §1 整数的次数
- §2 原根
- §3 计算次数的方法
- §4 计算原根的方法
- §5 原根的一个性质
- §6 指数
- §7 一般缩系的构造
- §8 原根的一个应用
- §9 基于离散对数的公钥密码体制
- §10 $k$ 次剩余
- §11 $k$ 次剩余符号 $\left(\frac{n}{p}\right)_k$
- 第六章 素性判别和整数分解
- §1 关于算法及其计算量
- §2 伪素数和素性判别
- §3 一些初等的素性判别方法
- §4 分解整数的费马方法和 Kraitchik 方法
- §5 连分数法和二次筛法
- §6 $p-1$ 法
第一章 整数的唯一分解定理
本章复习目标
本章是整个初等数论的地基。你需要会用整除关系、最大公因数、最小公倍数、素数分解和 Bezout 等式解决问题，并理解为什么“整数可以唯一分解为素数乘积”是许多定理的根源。
本章常考类型：
- 判断整除关系，证明整除命题。
- 用辗转相除法求 $(a,b)$，并反代求 Bezout 表示。
- 用唯一分解定理处理最大公因数、最小公倍数和指数比较。
- 解一次不定方程 $ax+by=c$。
- 用抽屉原理证明“必有两个对象满足某种同余/差值性质”。
知识点总览
| 小节 | 核心内容 | 复习重点 |
|---|---|---|
| §1 整除性 | $b\mid a$、倍数、因数、整除性质 | 会把整除翻译成等式 $a=bq$ |
| §2 最大公因数与辗转相除法 | $(a,b)$、Bezout 等式、欧几里得算法 | 反代求 $ax+by=(a,b)$ |
| §3 最小公倍数 | $[a,b]$ 与 $(a,b)$ 的关系 | $ab=(a,b)[a,b]$ 的适用条件 |
| §4 素数、整数的唯一分解定理 | 素数、合数、唯一分解 | 用素因子指数比较整除、gcd、lcm |
| §5 厄拉多塞筛法 | 素数筛选 | 只需筛到 $\sqrt n$ |
| §6 麦什涅数、费马数 | $M_p=2^p-1$、$F_n=2^{2^n}+1$ | 记住必要条件，不要误当充分条件 |
| §7 完全数 | $\sigma(n)=2n$ | 偶完全数与梅森素数相关 |
| §8 一次不定方程 | $ax+by=c$ | 有解条件 $(a,b)\mid c$，通解形式 |
| §9 抽屉原理 | 鸽巢原理 | 构造抽屉通常用余数类 |
按小节详细复习要点
§1 整除性。 这一节要把“整除”看成最基本的代数语言。考试中凡是出现 $a\mid b$，第一反应应是写成 $b=ak$；凡是要证明某数整除一个表达式，常把表达式整理成已知整除对象的整数线性组合。注意整除关系对符号不敏感：若 $a\mid b$，则 $-a\mid b$，$a\mid -b$，但通常把因数、公因数取为正数。
§2 最大公因数与辗转相除法。 最大公因数不只是一个数，还对应 Bezout 表示。会算 $(a,b)$ 只是第一步，更重要的是会反代得到 $ax+by=(a,b)$。许多同余逆元、一次不定方程都靠这一步。
§3 最小公倍数。 对两个正整数有 $(a,b)[a,b]=ab$。对多个整数时不要机械套用这个公式，通常回到素因子分解：最大公因数取各素因子最小指数，最小公倍数取最大指数。
§4 素数、整数的唯一分解定理。 这是本章主定理。证明题中若出现“若干整除条件共同成立”，通常可以把各整数写成素数幂，转化为指数不等式。例如 $a\mid b$ 等价于每个素数 $p$ 的指数满足 $v_p(a)\le v_p(b)$。
§5 厄拉多塞筛法。 判定 $n$ 以内的素数时，从 $2$ 开始划去倍数，只需要用不超过 $\sqrt n$ 的素数去筛。理由是合数必有一个不超过平方根的素因子。期末题中常把它作为“为什么试除到 $\sqrt n$ 足够”的依据。
§6 麦什涅数、费马数。 麦什涅数为 $M_p=2^p-1$。若 $2^n-1$ 是素数，则 $n$ 必是素数；反过来不成立。费马数为 $F_n=2^{2^n}+1$，有重要关系 \(F_0F_1\cdots F_{n-1}=F_n-2,\) 因此不同费马数两两互素。不要把“费马数两两互素”误记成“费马数全是素数”。
§7 完全数。 完全数满足真因子之和等于自身，等价于约数和函数 $\sigma(n)=2n$。欧几里得-欧拉定理说明：若 $2^p-1$ 是素数，则 \(2^{p-1}(2^p-1)\) 是偶完全数；并且每个偶完全数都可如此表示。它把完全数问题与麦什涅素数连接起来。
§8 一次不定方程。 $ax+by=c$ 的本质是 Bezout 等式乘倍数。先判 $(a,b)\mid c$，再求特解，最后写通解。若题目还要求正整数解，需要在通解中对参数 $t$ 加不等式限制。
§9 抽屉原理。 数论抽屉常用余数类。典型套路是构造 $n$ 个抽屉，却放入 $n+1$ 个对象。例如“任意 $n$ 个整数中存在非空子集，其和能被 $n$ 整除”，可考虑前缀和模 $n$ 的余数：若某个前缀和为 $0$，直接成立；否则 $n$ 个前缀和落入 $n-1$ 个非零余数类，必有两个同余，相减得到子集和被 $n$ 整除。
重要定义与定理
整除。 若存在整数 $q$ 使 $a=bq$，则称 $b$ 整除 $a$，记作 $b\mid a$。注意 $b\ne 0$。
常用性质：
- 若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$。
- 若 $a\mid b$ 且 $a\mid c$，则 $a\mid mb+nc$，其中 $m,n\in\mathbb Z$。
若 $a\mid b$ 且 $b\ne 0$，则 $ a \le b $。 - 若 $a\mid b$ 且 $b\mid a$，则 $a=\pm b$。
带余除法。 对整数 $a$ 和正整数 $b$，存在唯一整数 $q,r$ 使 \(a=bq+r,\qquad 0\le r<b.\) 这是辗转相除法的基础。
最大公因数。 $d=(a,b)$ 表示 $a,b$ 的最大正公因数。若 $(a,b)=1$，称 $a,b$ 互素。
Bezout 等式。 若 $d=(a,b)$，则存在整数 $x,y$，使 \(ax+by=d.\) 特别地，$(a,b)=1$ 当且仅当存在整数 $x,y$ 使 $ax+by=1$。
欧几里得引理。 若 $(a,b)=1$ 且 $a\mid bc$，则 $a\mid c$。特别地，若素数 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$。
最小公倍数。 $[a,b]$ 表示 $a,b$ 的最小正公倍数。对正整数 $a,b$， \((a,b)[a,b]=ab.\)
唯一分解定理。 任意大于 $1$ 的整数 $n$ 都可唯一写成 \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s},\) 其中 $p_1<\cdots<p_s$ 为素数，$\alpha_i$ 为正整数。唯一性指素数和指数都唯一。
若 \(a=\prod p_i^{\alpha_i},\qquad b=\prod p_i^{\beta_i},\) 把没有出现的素数指数看作 $0$，则 \((a,b)=\prod p_i^{\min(\alpha_i,\beta_i)},\qquad [a,b]=\prod p_i^{\max(\alpha_i,\beta_i)}.\)
一次不定方程。 方程 \(ax+by=c\) 有整数解当且仅当 $(a,b)\mid c$。若 $d=(a,b)$，且 $(x_0,y_0)$ 是一组特解，则全部整数解为 \(x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,\qquad t\in\mathbb Z.\)
抽屉原理。 若把 $n+1$ 个对象放入 $n$ 个抽屉，则至少有一个抽屉中有两个对象。数论中最常见的抽屉是“模 $m$ 的余数类”。
关键证明思路
带余除法的证明思路。 把所有形如 $a-bq$ 的非负整数放在一起，取其中最小者 $r$。若 $r\ge b$，则 $r-b$ 更小，矛盾；唯一性靠两个余数之差绝对值小于 $b$，又能被 $b$ 整除，只能为 $0$。
Bezout 等式的证明思路。 考虑集合 ${ax+by>0:x,y\in\mathbb Z}$ 的最小正元素 $d$，证明 $d\mid a$ 且 $d\mid b$，所以 $d$ 是公因数；同时任何公因数都整除 $ax+by$，所以 $d$ 是最大公因数。
唯一分解定理的证明思路。 存在性用反证或归纳：若有不能分解的最小整数，则它不是素数，写成两个较小因子的乘积，矛盾。唯一性用欧几里得引理：同一个素数必须出现在另一边，再约去，反复进行。
一次不定方程的证明思路。 必要性：若 $ax+by=c$，则 $(a,b)\mid c$。充分性：由 Bezout 等式 $ax_1+by_1=d$，乘以 $c/d$ 得特解。
常见题型与解法模板
题型 1：求最大公因数与 Bezout 表示。
- 用辗转相除法不断除到余数为 $0$。
- 最后一个非零余数就是 gcd。
- 从最后一步开始反代，把 gcd 表示为原来两个数的整数线性组合。
题型 2：证明整除命题。
优先考虑三种工具：
- 把 $a\mid b$ 写成 $b=ak$。
- 利用 $a\mid b$ 且 $a\mid c$ 推出 $a\mid mb+nc$。
- 若有互素条件，尝试用欧几里得引理。
题型 3：用唯一分解定理处理 gcd/lcm。
把所有数分解为素数幂，gcd 取较小指数，lcm 取较大指数。
题型 4：解 $ax+by=c$。
- 求 $d=(a,b)$。
- 若 $d\nmid c$，无整数解。
- 若 $d\mid c$，先解 $ax+by=d$，再乘以 $c/d$。
- 写通解。
题型 5：抽屉原理。
常见构造：
- 用余数 $0,1,\dots,m-1$ 作抽屉。
- 用部分和的余数作抽屉。
- 用区间分割作抽屉。
易错点
- $b\mid a$ 中被整除的是 $a$，不要读反。
- $(a,b)=1$ 不代表 $a,b$ 都是素数。
- $a\mid bc$ 不能直接推出 $a\mid b$ 或 $a\mid c$，除非 $a$ 是素数，或有互素条件。
- $2^p-1$ 若为素数，则 $p$ 必为素数；但 $p$ 是素数不保证 $2^p-1$ 是素数。
- 费马数两两互素，但不都为素数。
- 一次不定方程要先检查 $(a,b)\mid c$。
典型例题
例 1：求最大公因数和 Bezout 表示
求 $(252,198)$，并写成 $252x+198y=(252,198)$ 的形式。
解：
用辗转相除法： \(252=198+54,\) \(198=3\cdot54+36,\) \(54=36+18,\) \(36=2\cdot18.\) 所以 $(252,198)=18$。
反代： \(18=54-36.\) 又 \(36=198-3\cdot54,\) 所以 \(18=54-(198-3\cdot54)=4\cdot54-198.\) 又 \(54=252-198,\) 故 \(18=4(252-198)-198=4\cdot252-5\cdot198.\) 因此 \((252,198)=18,\qquad 18=4\cdot252-5\cdot198.\)
例 2：解一次不定方程
求整数解： \(84x+30y=18.\)
解：
先求 $(84,30)$： \(84=2\cdot30+24,\quad 30=24+6,\quad 24=4\cdot6,\) 所以 $(84,30)=6$。因为 $6\mid18$，方程有解。
先解 \(84x+30y=6.\) 反代： \(6=30-24=30-(84-2\cdot30)=3\cdot30-84.\) 即 \(6=-84+3\cdot30.\) 乘以 $3$，得 \(18=-3\cdot84+9\cdot30.\) 一组特解为 $x_0=-3,y_0=9$。
通解为 \(x=-3+\frac{30}{6}t=-3+5t,\) \(y=9-\frac{84}{6}t=9-14t,\) 其中 $t\in\mathbb Z$。
例 3：用唯一分解求 gcd 和 lcm
求 $a=2^3\cdot3^2\cdot5$ 与 $b=2\cdot3^4\cdot7$ 的最大公因数和最小公倍数。
解：
把没出现的素数指数补成 $0$： \(a=2^3\cdot3^2\cdot5^1\cdot7^0,\) \(b=2^1\cdot3^4\cdot5^0\cdot7^1.\) 最大公因数取较小指数： \((a,b)=2^1\cdot3^2=18.\) 最小公倍数取较大指数： \([a,b]=2^3\cdot3^4\cdot5\cdot7=22680.\)
例 4：证明一个整除命题
证明：若 $(a,b)=1$ 且 $a\mid c,\ b\mid c$，则 $ab\mid c$。
解：
因为 $a\mid c$，设 $c=ak$。又 $b\mid c$，所以 \(b\mid ak.\) 由于 $(a,b)=1$，由欧几里得引理得 \(b\mid k.\) 设 $k=bt$，则 \(c=ak=abt.\) 因此 $ab\mid c$。
例 5：抽屉原理
证明：任意给定 $n+1$ 个整数，其中必有两个数之差能被 $n$ 整除。
解：
每个整数除以 $n$ 的余数只能是 \(0,1,\dots,n-1,\) 共 $n$ 种。把 $n+1$ 个整数按模 $n$ 的余数放入这 $n$ 个抽屉。由抽屉原理，至少有两个整数落入同一个抽屉，即它们模 $n$ 同余。
若这两个整数为 $a,b$，则 \(a\equiv b\pmod n,\) 所以 \(n\mid(a-b).\)
第二章 同余式
本章复习目标
本章把“整除”改写为“同余”，是后面数论函数、二次剩余、原根和素性判别的语言基础。你要特别熟悉同余运算的合法变形、线性同余的解法、中国剩余定理，以及模素数/素数幂时方程解数的变化。
本章常考类型：
- 化简同余式。
- 解一次同余式 $ax\equiv b\pmod m$。
- 解同余式组。
- 判断能否约去公因子。
- 运用费马小定理、Wilson 定理等处理模素数问题。
- 了解覆盖同余组的含义和判断方法。
知识点总览
| 小节 | 核心内容 | 复习重点 |
|---|---|---|
| §1 同余的定义和基本性质 | $a\equiv b\pmod m$ | 同余等价于 $m\mid a-b$ |
| §2 剩余类和完全剩余系 | 模 $m$ 的剩余类 | 完全剩余系的判别 |
| §3 缩系 | 与模数互素的剩余类 | 缩系个数为 $\varphi(m)$ |
| §4 一次同余式 | $ax\equiv b\pmod m$ | 有解条件 $(a,m)\mid b$ |
| §5 模数是素数的同余式 | 模 $p$ 多项式同余 | 次数与根数关系，费马小定理 |
| §6 孙子剩余定理及其应用举例 | 中国剩余定理 | 两两互素模数时唯一解模乘积 |
| §7 模数是素数幂的同余式 | 从模 $p$ 提升到模 $p^k$ | 注意解的提升条件 |
| §8 整数的剩余表示 | 用剩余表示整数 | 常用于计算和编码 |
| §9 逐步淘汰原则 | 分步筛选满足条件的数 | 与同余组结合 |
| §10 Wolstenholme 定理的推广 | 调和和同余 | 重点掌握结论形态和适用条件 |
| §11 覆盖同余式组 | 若干同余类覆盖整数 | 会判断简单覆盖 |
按小节详细复习要点
§1 同余的定义和基本性质。 同余是整除的改写：$a\equiv b\pmod m$ 就是 $m\mid a-b$。同余可以加、减、乘、乘方，但不能随意除。约去公共因子时模数也可能改变，这是本章最容易错的地方。
§2 剩余类和完全剩余系。 模 $m$ 的整数被分成 $m$ 个剩余类。判断一组 $m$ 个数是不是完全剩余系，只需看它们模 $m$ 是否两两不同余。常用判据：若 $(a,m)=1$，则当 $x$ 跑遍完全剩余系时，$ax+b$ 也跑遍完全剩余系。
§3 缩系。 缩系只保留与模数互素的剩余类。若 $(a,m)=1$，乘以 $a$ 会把缩系置换成缩系，这是 Euler 定理证明的关键。缩系的元素个数是 $\varphi(m)$。
§4 一次同余式。 $ax\equiv b\pmod m$ 等价于 $ax-my=b$，所以有解条件是 $(a,m)\mid b$。求解时要注意：如果 $d=(a,m)>1$ 且 $d\mid b$，则模 $m$ 下有 $d$ 个不同余解。
§5 模数是素数的同余式。 模素数 $p$ 时，非零剩余类构成乘法群，很多结论变得干净。常用事实：次数不超过 $n$ 的非零多项式模 $p$ 最多有 $n$ 个根；$x^{p-1}\equiv1\pmod p$ 对 $p\nmid x$ 成立；$(p-1)!\equiv-1\pmod p$。
§6 孙子剩余定理及其应用举例。 当模数两两互素时，同余式组有唯一解模乘积。构造解的思想是制造“选择器”：某一项在自己的模数下等于 $1$，在其他模数下等于 $0$。这也是整数剩余表示、RSA 解密加速的基础。
§7 模数是素数幂的同余式。 从模 $p$ 到模 $p^k$ 时，解的情况可能变化。常用思想是“提升”：先解模 $p$，再设 $x=a+pt$ 代回，逐步确定 $t$。若多项式 $f(a)\equiv0\pmod p$ 且 $f’(a)\not\equiv0\pmod p$，通常可唯一提升到模 $p^k$ 的解；若导数也被 $p$ 整除，就要额外分析。
§8 整数的剩余表示。 若 $m_1,\dots,m_k$ 两两互素，则一个整数模 $M=m_1\cdots m_k$ 可由它对各 $m_i$ 的余数组 \((x\bmod m_1,\dots,x\bmod m_k)\) 唯一表示。优点是加法、乘法可分量进行，最后再用孙子定理还原。
§9 逐步淘汰原则。 这是筛选思想：先用一个同余条件筛掉大部分数，再加入第二个条件，逐步缩小候选集合。解题时常把它写成“先模 $m_1$，再模 $m_2$，最后合并为模 $[m_1,m_2,\dots]$ 的剩余类”。
§10 Wolstenholme 定理的推广。 基本 Wolstenholme 定理说：若 $p\ge5$ 为素数，则 \(\binom{2p-1}{p-1}\equiv1\pmod {p^3},\) 等价地常写为 \(\sum_{i=1}^{p-1}\frac1i\equiv0\pmod {p^2}.\) 这里的分数在模 $p^2$ 意义下解释为逆元。复习时重点掌握它用于处理调和和同余，不必把长证明逐行背下。
§11 覆盖同余式组。 若若干同余类覆盖所有整数，就是覆盖同余式组。检查时统一到最小公倍数 $L$，把每个同余类展开成模 $L$ 的剩余类，看是否覆盖 $0,1,\dots,L-1$。
重要定义与定理
同余。 若 $m\mid a-b$，称 $a$ 与 $b$ 模 $m$ 同余，记作 \(a\equiv b\pmod m.\)
同余的基本性质：
- 自反性：$a\equiv a\pmod m$。
- 对称性：若 $a\equiv b\pmod m$，则 $b\equiv a\pmod m$。
- 传递性：若 $a\equiv b\pmod m,\ b\equiv c\pmod m$，则 $a\equiv c\pmod m$。
- 可加减乘：若 $a\equiv b,\ c\equiv d\pmod m$，则 \(a\pm c\equiv b\pm d\pmod m,\qquad ac\equiv bd\pmod m.\)
约去规则。 若 \(ac\equiv bc\pmod m,\) 且 $d=(c,m)$，则 \(a\equiv b\pmod {m/d}.\) 只有当 $(c,m)=1$ 时，才能直接约去 $c$，得到 $a\equiv b\pmod m$。
完全剩余系。 若 $m$ 个整数模 $m$ 两两不同余，则它们构成模 $m$ 的一个完全剩余系。
缩系。 在模 $m$ 的一个完全剩余系中，与 $m$ 互素的那些剩余类组成模 $m$ 的一个缩系。缩系元素个数为欧拉函数 $\varphi(m)$。
一次同余式。 同余式 \(ax\equiv b\pmod m\) 有解当且仅当 \((a,m)\mid b.\) 若 $d=(a,m)$ 且 $d\mid b$，则恰有 $d$ 个模 $m$ 不同余的解。化为 \(\frac a d x\equiv \frac b d\pmod {m/d},\) 再利用 $\left(\frac a d,\frac m d\right)=1$ 求逆元。
费马小定理。 若 $p$ 是素数且 $p\nmid a$，则 \(a^{p-1}\equiv1\pmod p.\) 等价形式： \(a^p\equiv a\pmod p.\)
Wilson 定理。 对素数 $p$， \((p-1)!\equiv -1\pmod p.\) 反过来，若 $n>1$ 且 $(n-1)!\equiv -1\pmod n$，则 $n$ 是素数。
孙子剩余定理。 若 $m_1,\dots,m_k$ 两两互素，则同余式组 \(x\equiv a_i\pmod {m_i}\qquad (i=1,\dots,k)\) 在模 \(M=m_1m_2\cdots m_k\) 意义下存在唯一解。
构造方法：令 $M_i=M/m_i$，取 $N_i$ 满足 \(M_iN_i\equiv1\pmod {m_i},\) 则 \(x\equiv\sum_{i=1}^k a_iM_iN_i\pmod M.\)
覆盖同余式组。 若若干同余类 \(x\equiv a_i\pmod {m_i}\) 的并包含所有整数，则称它们组成覆盖同余式组。判断时常把若干模数统一到最小公倍数，然后检查所有剩余类是否被覆盖。
关键证明思路
同余性质的证明思路。 全部从定义 $m\mid a-b$ 出发。例如乘法性质：若 $a-b=mu,\ c-d=mv$，则 \(ac-bd=c(a-b)+b(c-d)=m(cu+bv),\) 所以 $ac\equiv bd\pmod m$。
一次同余式解法的证明思路。 $ax\equiv b\pmod m$ 等价于 $ax-my=b$，这是一次不定方程。于是有解条件就是 $(a,m)\mid b$。
孙子剩余定理的证明思路。 构造 $M_i=M/m_i$。因为 $M_i$ 被除 $m_i$ 外的每个模数整除，所以 $M_iN_i$ 在第 $i$ 个模数下为 $1$，在其他模数下为 $0$。这些“选择器”相加即可得到解。
常见题型与解法模板
题型 1：解 $ax\equiv b\pmod m$。
- 求 $d=(a,m)$。
- 若 $d\nmid b$，无解。
- 若 $d\mid b$，约化为 $\frac a d x\equiv \frac b d\pmod {m/d}$。
- 求 $\frac a d$ 的逆元。
- 写出模 $m$ 下的 $d$ 个解。
题型 2：中国剩余定理。
- 检查模数是否两两互素。
- 计算 $M=\prod m_i$。
- 对每个 $i$，令 $M_i=M/m_i$。
- 求 $M_i$ 关于模 $m_i$ 的逆元 $N_i$。
- 用 $x\equiv\sum a_iM_iN_i\pmod M$。
题型 3：模素数的多项式同余。
常用工具：
- 费马小定理降幂。
- Wilson 定理处理阶乘。
- 若非零多项式 $f(x)$ 在模素数 $p$ 下次数为 $n$，通常根数不超过 $n$，但要注意“多项式是否恒为零模 $p$”。
题型 4：覆盖同余式组。
- 取模数最小公倍数 $L$。
- 把每个同余类展开为模 $L$ 的若干剩余类。
- 看是否覆盖 $0,1,\dots,L-1$。
易错点
- 同余式中乘法可以直接乘，但除法不总是合法。
- $a\equiv b\pmod m$ 和 $a\equiv b\pmod n$ 不一定推出模 $mn$ 同余，除非 $(m,n)=1$。
- 中国剩余定理的唯一性是在模 $M$ 意义下。
- 一次同余有 $d=(a,m)$ 个模 $m$ 不同余解，不是一个解。
- 费马小定理要求 $p$ 是素数且 $p\nmid a$。
- Wilson 定理计算量大，理论价值大于手算价值。
典型例题
例 1：解一次同余式
解 \(14x\equiv 30\pmod {100}.\)
解：
求 \((14,100)=2.\) 因为 $2\mid30$，所以有解，且模 $100$ 下有 $2$ 个不同余解。
两边除以 $2$： \(7x\equiv15\pmod {50}.\) 求 $7$ 模 $50$ 的逆元。因为 \(50=7\cdot7+1,\) 所以 \(1=50-7\cdot7,\) 故 \(7^{-1}\equiv -7\equiv43\pmod {50}.\) 于是 \(x\equiv15\cdot43=645\equiv45\pmod {50}.\) 在模 $100$ 下，解为 \(x\equiv45,\ 95\pmod {100}.\)
例 2：解中国剩余问题
解同余式组 \(x\equiv2\pmod3,\qquad x\equiv3\pmod5,\qquad x\equiv2\pmod7.\)
解：
模数 $3,5,7$ 两两互素，故有唯一解模 \(M=3\cdot5\cdot7=105.\)
令 \(M_1=35,\quad M_2=21,\quad M_3=15.\) 求逆元： \(35\equiv2\pmod3,\quad 2^{-1}\equiv2\pmod3,\) 所以 $N_1=2$。 \(21\equiv1\pmod5,\quad N_2=1.\) \(15\equiv1\pmod7,\quad N_3=1.\) 因此 \(x\equiv2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1\pmod {105}.\) 即 \(x\equiv140+63+30=233\equiv23\pmod {105}.\)
例 3：Wilson 定理应用
求 $18!$ 模 $19$ 的余数。
解：
因为 $19$ 是素数，由 Wilson 定理， \((19-1)!=18!\equiv-1\pmod {19}.\) 所以 \(18!\equiv18\pmod {19}.\)
例 4：用费马小定理降幂
求 $7^{222}$ 除以 $13$ 的余数。
解：
因为 $13$ 是素数且 $(7,13)=1$，由费马小定理 \(7^{12}\equiv1\pmod {13}.\) 又 \(222=12\cdot18+6,\) 所以 \(7^{222}\equiv7^6\pmod {13}.\) 计算： \(7^2=49\equiv10\pmod {13},\) \(7^4\equiv10^2=100\equiv9\pmod {13},\) \(7^6\equiv7^4\cdot7^2\equiv9\cdot10=90\equiv12\pmod {13}.\) 因此余数是 $12$。
例 5：判断覆盖同余式组
判断下面三个同余类是否覆盖所有整数： \(x\equiv0\pmod2,\qquad x\equiv1\pmod4,\qquad x\equiv3\pmod4.\)
解：
统一到模 $4$。
- $x\equiv0\pmod2$ 对应模 $4$ 的 $0,2$。
- $x\equiv1\pmod4$ 对应 $1$。
- $x\equiv3\pmod4$ 对应 $3$。
模 $4$ 的剩余类 $0,1,2,3$ 全部被覆盖。因此这三个同余类覆盖所有整数。
第三章 数论函数
本章复习目标
本章把整数 $n$ 映到某个数值的函数作为研究对象。最重要的是 $\mu(n)$、$\varphi(n)$、狄利克雷乘积、Mobius 反演和积性函数。它们常出现在求和、计数、同余和密码学中。
本章常考类型：
- 计算 $\mathrm{pot}_p n$、$\mu(n)$、$\varphi(n)$。
- 判断函数是否积性。
- 使用狄利克雷乘积。
- 用 Mobius 反演从一个求和关系反推出原函数。
- 理解 RSA 的基本数学结构。
知识点总览
| 小节 | 核心内容 | 复习重点 |
|---|---|---|
| §1 数论函数 $\mathrm{pot}_p n$ | $p$ 在 $n$ 中出现的指数 | $p^\alpha\mid n$ 但 $p^{\alpha+1}\nmid n$ |
| §2 麦比乌斯函数 $\mu(n)$ | 判断平方因子与素因子个数 | $\mu(n)=0,\pm1$ |
| §3 欧拉函数 $\varphi(n)$ | 小于等于 $n$ 且与 $n$ 互素的数个数 | 公式 $\varphi(n)=n\prod_{p\mid n}(1-1/p)$ |
| §4 数论函数的狄利克雷乘积 | $(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)$ | 单位函数与恒等函数关系 |
| §5 麦比乌斯反演公式 | 从 $F(n)=\sum_{d\mid n}f(d)$ 反求 $f$ | $f(n)=\sum_{d\mid n}\mu(d)F(n/d)$ |
| §6 积性函数 | $(m,n)=1$ 时 $f(mn)=f(m)f(n)$ | 积性函数由素数幂决定 |
| §7 数论函数 $\pi(n)$ | 不超过 $n$ 的素数个数 | 理解素数分布问题 |
| §8 卢卡斯序列 | 递推序列 | 关注递推和模运算 |
| §9 陷门单向函数与公开密钥码 | RSA 思想 | 乘法容易，分解困难 |
按小节详细复习要点
§1 数论函数 $\mathrm{pot}_p n$。 $\mathrm{pot}_p n$ 记录素数 $p$ 在 $n$ 中出现的指数，也常记为 $v_p(n)$。它把整除问题转化为指数问题：$a\mid b$ 当且仅当对所有素数 $p$，都有 $v_p(a)\le v_p(b)$。
§2 麦比乌斯函数 $\mu(n)$。 $\mu(n)$ 用来识别“无平方因子”并记录素因子个数奇偶。最重要恒等式是 $\sum_{d\mid n}\mu(d)=0$（$n>1$），它是反演公式的发动机。
§3 欧拉函数 $\varphi(n)$。 $\varphi(n)$ 是缩系大小。对素数幂 $p^\alpha$， \(\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}.\) 一般 $n$ 用乘积公式。看到 $(a,n)=1$ 的幂同余，优先考虑 Euler 定理降幂。
§4 数论函数的狄利克雷乘积。 狄利克雷乘积把“对约数求和”变成函数乘法。常用记号：$1(n)=1$，$\varepsilon(1)=1,\varepsilon(n)=0(n>1)$。核心关系是 $\mu*1=\varepsilon$。
§5 麦比乌斯反演公式。 只要题目给出 $F(n)=\sum_{d\mid n}f(d)$，就可以反演。反演本质是“去掉所有约数求和带来的累积影响”。这类题要特别注意 $F(d)$ 和 $F(n/d)$ 的位置。
§6 积性函数。 积性函数满足互素可乘。证明积性时常把 $mn$ 的约数唯一写为 $d_1d_2$，其中 $d_1\mid m,d_2\mid n$。积性函数由素数幂上的取值完全决定。
§7 数论函数 $\pi(n)$。 $\pi(n)$ 表示不超过 $n$ 的素数个数。它连接素数分布问题。初等复习中重点知道它不是简单积性函数，也不像 $\varphi,\mu$ 那样由约数公式直接给出。
§8 卢卡斯序列。 卢卡斯序列是一类二阶递推序列，常写为 \(U_0=0,\quad U_1=1,\quad U_{n+2}=PU_{n+1}-QU_n.\) 它的复习重点是递推、同余周期和可用于构造素性测试的思想。遇到卢卡斯序列题时，先由初值递推列项，再观察模数下的周期或整除关系。
§9 陷门单向函数与公开密钥码。 “单向”指正向计算容易，反向困难；“陷门”指掌握秘密信息后反向也容易。RSA 中公开 $N=pq$ 和加密指数 $e$，保密 $p,q$ 或 $\varphi(N)$，因为知道分解后才能求解密指数。
重要定义与定理
数论函数。 定义在正整数上的函数称为数论函数，如 $\mu(n),\varphi(n),\tau(n),\sigma(n)$。
$\mathrm{pot}_p n$。 对素数 $p$，若 \(p^\alpha\mid n,\qquad p^{\alpha+1}\nmid n,\) 则记 \(\mathrm{pot}_p n=\alpha.\) 它就是 $n$ 的素因子分解中 $p$ 的指数。
Mobius 函数。 \(\mu(n)= \begin{cases} 1, & n=1,\\ (-1)^r, & n=p_1p_2\cdots p_r,\ p_i\text{ 互异素数},\\ 0, & \text{若 }n\text{ 含有平方因子}. \end{cases}\)
重要恒等式： \(\sum_{d\mid n}\mu(d)= \begin{cases} 1, & n=1,\\ 0, & n>1. \end{cases}\)
欧拉函数。 $\varphi(n)$ 表示 $1,2,\dots,n$ 中与 $n$ 互素的整数个数。若 \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s},\) 则 \(\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right) =\prod_{i=1}^s p_i^{\alpha_i-1}(p_i-1).\)
Euler 定理。 若 $(a,n)=1$，则 \(a^{\varphi(n)}\equiv1\pmod n.\) 费马小定理是 $n=p$ 时的特例。
狄利克雷乘积。 对数论函数 $f,g$，定义 \((f*g)(n)=\sum_{d\mid n}f(d)g\left(\frac nd\right).\) 记常函数 $1(n)=1$，单位函数 \(\varepsilon(n)= \begin{cases} 1, & n=1,\\ 0, & n>1. \end{cases}\) 则 \(\mu*1=\varepsilon.\)
Mobius 反演。 若 \(F(n)=\sum_{d\mid n}f(d),\) 则 \(f(n)=\sum_{d\mid n}\mu(d)F\left(\frac nd\right).\) 等价写法：若 $F=f1$，则 $f=F\mu$。
积性函数。 若 $f(1)=1$，且当 $(m,n)=1$ 时 \(f(mn)=f(m)f(n),\) 则称 $f$ 为积性函数。若对所有 $m,n$ 都成立，则称完全积性函数。
常见积性函数：
- $\mu(n)$ 是积性函数。
- $\varphi(n)$ 是积性函数。
- $\tau(n)=\sum_{d\mid n}1$ 是积性函数。
- $\sigma(n)=\sum_{d\mid n}d$ 是积性函数。
若 $f,g$ 积性，则 $f*g$ 也积性。
RSA 基本思想。 取大素数 $p,q$，令 $N=pq$，则 \(\varphi(N)=(p-1)(q-1).\) 选 $e$ 满足 $(e,\varphi(N))=1$，再取 $d$ 满足 \(ed\equiv1\pmod{\varphi(N)}.\) 加密 $C\equiv M^e\pmod N$，解密 $M\equiv C^d\pmod N$。公开 $N,e$，保密 $d,p,q$。安全性依赖“大整数分解困难”。
关键证明思路
$\sum_{d\mid n}\mu(d)$ 的证明思路。 若 $n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}$，只有无平方因子的约数对 $\mu$ 有贡献，所以 \(\sum_{d\mid n}\mu(d)=\sum_{k=0}^s \binom{s}{k}(-1)^k=(1-1)^s.\) 当 $n>1$ 时 $s\ge1$，和为 $0$；当 $n=1$ 时和为 $1$。
欧拉函数公式的证明思路。 在 $1,\dots,n$ 中删去所有被 $p_i$ 整除的数。用容斥原理得到 \(n\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_s}\right).\)
Mobius 反演的证明思路。 若 $F=f*1$，两边与 $\mu$ 作狄利克雷乘积： \(F*\mu=f*1*\mu=f*\varepsilon=f.\)
积性函数由素数幂决定。 若 $n=\prod p_i^{\alpha_i}$，各素数幂两两互素，故 \(f(n)=\prod f(p_i^{\alpha_i}).\)
常见题型与解法模板
题型 1：计算 $\mu(n)$。
- 分解 $n$。
- 若有某个素数指数 $\ge2$，则 $\mu(n)=0$。
- 若 $n$ 是 $r$ 个互异素数的乘积，则 $\mu(n)=(-1)^r$。
题型 2：计算 $\varphi(n)$。
- 分解 $n$。
- 用 \(\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).\)
题型 3：做 Mobius 反演。
看到 \(F(n)=\sum_{d\mid n} f(d)\) 就立刻写 \(f(n)=\sum_{d\mid n}\mu(d)F(n/d).\) 若是 \(F(n)=\sum_{d\mid n}f(n/d),\) 本质相同，因为 $d$ 与 $n/d$ 都跑遍全部约数。
题型 4：判断积性函数。
不要用随便两个数验证。要证明对任意互素 $m,n$，有 $f(mn)=f(m)f(n)$。如果函数由“约数求和”给出，经常可用约数一一对应： \(d\mid mn,\ (m,n)=1\) 等价于 \(d=d_1d_2,\quad d_1\mid m,\ d_2\mid n.\)
易错点
- $\mu(n)=0$ 的条件是含有平方因子，不是含有偶数个素因子。
- $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$。
- $\varphi$ 是积性函数，但不是完全积性函数。例如 $\varphi(4)\ne\varphi(2)\varphi(2)$。
- Mobius 反演中变量 $d$ 和 $n/d$ 可互换，但不要把 $F(d)$ 与 $F(n/d)$ 写错。
- RSA 中 $e$ 和 $\varphi(N)$ 必须互素，否则不能求解密指数 $d$。
典型例题
例 1：计算 $\mu(n)$ 与 $\varphi(n)$
计算 $n=2^3\cdot3^2\cdot5=360$ 的 $\mu(n)$ 与 $\varphi(n)$。
解：
因为 $360$ 含有平方因子 $2^2$ 和 $3^2$，所以 \(\mu(360)=0.\)
欧拉函数为 \(\varphi(360)=360\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right).\) 计算得 \(\varphi(360)=360\cdot\frac12\cdot\frac23\cdot\frac45=96.\)
例 2：狄利克雷乘积
设 $1(n)=1$，$\mathrm{id}(n)=n$。求 \((1*\mathrm{id})(n).\)
解：
由定义 \((1*\mathrm{id})(n)=\sum_{d\mid n}1(d)\mathrm{id}(n/d) =\sum_{d\mid n}\frac nd.\) 当 $d$ 跑遍 $n$ 的约数时，$n/d$ 也跑遍 $n$ 的全部约数，所以 \((1*\mathrm{id})(n)=\sum_{d\mid n}d=\sigma(n).\)
例 3：Mobius 反演
已知 \(F(n)=\sum_{d\mid n} f(d).\) 若 $F(n)=n$，求 $f(n)$。
解：
由 Mobius 反演， \(f(n)=\sum_{d\mid n}\mu(d)F(n/d) =\sum_{d\mid n}\mu(d)\frac nd.\) 因此 \(f(n)=n\sum_{d\mid n}\frac{\mu(d)}d.\) 这个函数正是欧拉函数： \(f(n)=\varphi(n).\) 也就是说 \(\sum_{d\mid n}\varphi(d)=n.\)
例 4：证明 $\varphi$ 是积性函数
证明：若 $(m,n)=1$，则 \(\varphi(mn)=\varphi(m)\varphi(n).\)
解：
设 \(m=\prod p_i^{\alpha_i},\qquad n=\prod q_j^{\beta_j}.\) 因为 $(m,n)=1$，所以 $p_i$ 与 $q_j$ 没有重复。于是 \(\varphi(mn)=mn\prod_{p\mid mn}\left(1-\frac1p\right).\) 拆成两部分： \(\varphi(mn) =m\prod_{p\mid m}\left(1-\frac1p\right) \cdot n\prod_{q\mid n}\left(1-\frac1q\right).\) 故 \(\varphi(mn)=\varphi(m)\varphi(n).\)
例 5：RSA 小例
取 $p=5,q=11$，令 $N=55$。取 $e=3$。求解密指数 $d$，并解密密文 $C=8$。
解：
先算 \(\varphi(N)=(5-1)(11-1)=40.\) 要求 \(3d\equiv1\pmod {40}.\) 因为 \(3\cdot27=81\equiv1\pmod {40},\) 所以 $d=27$。
解密： \(M\equiv C^d\equiv8^{27}\pmod {55}.\) 直接算较麻烦，可以用中国剩余定理。
模 $5$： \(8\equiv3,\quad 3^4\equiv1\pmod5,\quad 27\equiv3\pmod4,\) 所以 \(8^{27}\equiv3^3=27\equiv2\pmod5.\)
模 $11$： \(8^2=64\equiv9,\quad 8^5\equiv10\equiv-1\pmod {11},\) 故 \(8^{10}\equiv1\pmod {11}.\) 由于 $27\equiv7\pmod{10}$， \(8^{27}\equiv8^7=8^5\cdot8^2\equiv(-1)\cdot9\equiv2\pmod {11}.\) 于是 \(M\equiv2\pmod5,\qquad M\equiv2\pmod {11},\) 所以 \(M\equiv2\pmod {55}.\)
第四章 二次剩余
本章复习目标
本章研究平方同余 \(x^2\equiv a\pmod m\) 是否有解。核心是勒让德符号、欧拉判别法、高斯引理和二次互反律。期末中这一章通常计算性很强：会不会快速化简符号，往往决定能不能做完题。
本章常考类型：
- 判断 $a$ 是否为模 $p$ 的二次剩余。
- 计算勒让德符号和雅可比符号。
- 使用二次互反律。
- 解二次同余式。
- 判断素数或整数能否表示成平方和。
知识点总览
| 小节 | 核心内容 | 复习重点 |
|---|---|---|
| §1 二次剩余 | $x^2\equiv a\pmod p$ | 剩余与非剩余的定义 |
| §2 勒让德符号 | $\left(\frac ap\right)$ | 欧拉判别法 |
| §3 高斯引理 | 用最小正剩余判断符号 | 二次互反律的证明工具 |
| §4 二次互反律 | 两个奇素数间的符号转换 | 符号变化条件 |
| §5 二次剩余理论应用举例 | 快速判别与计算 | 熟练化简 |
| §6 二次同余式的解法和解数 | 解 $x^2\equiv a\pmod m$ | 先分解模数，再合并 |
| §7 雅可比符号 | 推广勒让德符号 | 值为 $1$ 不一定有解 |
| §8 表素数为平方和 | $p=x^2+y^2$ | $p=2$ 或 $p\equiv1\pmod4$ |
| §9 表正整数为平方和 | 两平方和定理 | $4k+3$ 型素因子指数须为偶数 |
按小节详细复习要点
§1 二次剩余。 对奇素数 $p$，非零平方剩余共有 $(p-1)/2$ 个，非剩余也有 $(p-1)/2$ 个。平方剩余集合来自 $1^2,2^2,\dots,((p-1)/2)^2$，因为 $x^2$ 与 $(-x)^2$ 相同。
§2 勒让德符号。 勒让德符号把“是否有平方根”压缩成 $0,\pm1$。计算时必须保证分母是奇素数。最常用工具是乘法性、欧拉判别法、$-1$ 与 $2$ 的补充公式。
§3 高斯引理。 高斯引理通常不是直接出计算题，而是用来理解二次互反律。它把 $\left(\frac ap\right)$ 转化为 $a,2a,\dots,\frac{p-1}{2}a$ 的最小绝对剩余中负数个数的奇偶。
§4 二次互反律。 这是本章核心计算工具。翻转 $\left(\frac pq\right)$ 时只需记一句话：两个奇素数都为 $3\bmod4$ 才变号，否则不变号。
§5 二次剩余理论应用举例。 典型应用包括快速判别同余方程是否有解、计算大分子的勒让德符号、证明某些素数表示形式的必要条件。做题时先化简符号，再决定是否需要实际求根。
§6 二次同余式的解法和解数。 模奇素数时，$\left(\frac ap\right)=1$ 给两个解，$-1$ 无解，$0$ 给一个解。模合数时先分解模数，再分别求解并用孙子定理合并；总解数通常是各部分解数的乘积。
§7 雅可比符号。 雅可比符号可以像勒让德符号一样用互反律快速计算，但逻辑含义弱一些。若 $\left(\frac an\right)=-1$，则 $a$ 一定不是模 $n$ 的平方；若等于 $1$，不能断定有平方根。
§8 表素数为平方和。 奇素数 $p$ 能写成 $x^2+y^2$ 当且仅当 $p\equiv1\pmod4$。必要性来自 $-1$ 必须是模 $p$ 的二次剩余；充分性较深，复习时记住定理和常见构造题即可。
§9 表正整数为平方和。 正整数 $n$ 可写成两个平方和，当且仅当所有 $4k+3$ 型素因子的指数为偶数。判断题只需分解质因数并检查这一条。
重要定义与定理
二次剩余。 设 $p$ 是奇素数，$p\nmid a$。若同余式 \(x^2\equiv a\pmod p\) 有解，则称 $a$ 是模 $p$ 的二次剩余；否则称为二次非剩余。
勒让德符号。 \(\left(\frac ap\right)= \begin{cases} 1, & a\text{ 是模 }p\text{ 的二次剩余},\\ -1, & a\text{ 是模 }p\text{ 的二次非剩余},\\ 0, & p\mid a. \end{cases}\)
基本性质：
- 若 $a\equiv b\pmod p$，则 \(\left(\frac ap\right)=\left(\frac bp\right).\)
- 乘法性： \(\left(\frac {ab}p\right)=\left(\frac ap\right)\left(\frac bp\right).\)
欧拉判别法。 对奇素数 $p$， \(\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p.\) 由于左边为 $0,\pm1$，实际使用时是： \(a^{(p-1)/2}\equiv \begin{cases} 1\pmod p, & a\text{ 是二次剩余},\\ -1\pmod p, & a\text{ 是二次非剩余}. \end{cases}\)
两个补充公式。 \(\left(\frac {-1}p\right)=(-1)^{(p-1)/2} = \begin{cases} 1,&p\equiv1\pmod4,\\ -1,&p\equiv3\pmod4. \end{cases}\)
\[\left(\frac 2p\right)=(-1)^{(p^2-1)/8} = \begin{cases} 1,&p\equiv\pm1\pmod8,\\ -1,&p\equiv\pm3\pmod8. \end{cases}\]二次互反律。 若 $p,q$ 是不同奇素数，则 \(\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.\) 也就是说：
- 若 $p,q$ 中至少一个 $\equiv1\pmod4$，则 \(\left(\frac pq\right)=\left(\frac qp\right).\)
- 若 $p\equiv q\equiv3\pmod4$，则 \(\left(\frac pq\right)=-\left(\frac qp\right).\)
雅可比符号。 若 $n$ 为正奇数， \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s},\) 定义 \(\left(\frac an\right)= \prod_{i=1}^s\left(\frac a{p_i}\right)^{\alpha_i}.\) 当 $n$ 为素数时，雅可比符号就是勒让德符号。注意：若 $\left(\frac an\right)=-1$，则 $a$ 一定不是模 $n$ 的平方；但若 $\left(\frac an\right)=1$，不一定有解。
平方和定理。
- 奇素数 $p$ 可表示为两个平方数之和，当且仅当 \(p\equiv1\pmod4.\) 另外 $2=1^2+1^2$。
- 正整数 $n$ 可表示为两个平方数之和，当且仅当在 $n$ 的素因子分解中，每个形如 $4k+3$ 的素数的指数都是偶数。
关键证明思路
欧拉判别法的证明思路。 模 $p$ 的非零剩余类组成乘法群。平方剩余正好是平方映射的像，共 $(p-1)/2$ 个。利用费马小定理和多项式根数可说明：二次剩余满足 $a^{(p-1)/2}\equiv1$，非剩余满足 $a^{(p-1)/2}\equiv-1$。
高斯引理的证明思路。 观察 \(a,2a,\dots,\frac{p-1}{2}a\) 模 $p$ 的最小绝对剩余。若其中有 $\mu$ 个为负，则 \(\left(\frac ap\right)=(-1)^\mu.\) 它把符号计算转化为“数负号个数”。
二次互反律的证明思路。 对 $p,q$ 分别应用高斯引理，把符号转化为两个格点计数问题；两个计数和覆盖一个矩形区域，所以符号乘积由矩形面积的奇偶决定。
平方和定理的证明思路。 若 $p=x^2+y^2$ 且 $p$ 为奇素数，则 $-1\equiv (xy^{-1})^2\pmod p$，所以 $\left(\frac{-1}p\right)=1$，得 $p\equiv1\pmod4$。反向证明可用二次剩余与最小值/鸽巢思想构造。
常见题型与解法模板
题型 1：计算勒让德符号。
- 先把分子化为模 $p$ 的小整数。
- 分解分子，用乘法性拆开。
- 遇到 $-1$、$2$ 用补充公式。
- 遇到奇素数用二次互反律翻转。
- 重复直到分子很小。
题型 2：判断 $x^2\equiv a\pmod p$ 是否有解。
计算 $\left(\frac ap\right)$：
- 等于 $1$：有两个不同解模 $p$。
- 等于 $-1$：无解。
- 等于 $0$：有唯一解 $x\equiv0\pmod p$，前提是 $p\mid a$。
题型 3：解 $x^2\equiv a\pmod m$。
- 分解 $m$ 为素数幂。
- 分别解模每个素数幂。
- 用中国剩余定理合并。
题型 4：用雅可比符号。
雅可比符号适合快速判别“不可能”。若值为 $-1$，无平方解；若值为 $1$，还要进一步检查。
易错点
- 勒让德符号分母必须是奇素数。
- 雅可比符号分母可以是奇合数，但 $\left(\frac an\right)=1$ 不保证 $a$ 是二次剩余。
- 二次互反律翻转时，只有两个奇素数都 $\equiv3\pmod4$ 才变号。
- $\left(\frac 2p\right)$ 看的是 $p\bmod 8$，不是 $p\bmod4$。
- 解二次同余模合数时，不能只看雅可比符号。
典型例题
例 1：判断二次剩余
判断 $5$ 是否为模 $11$ 的二次剩余。
解：
计算平方： \(1^2\equiv1,\quad 2^2\equiv4,\quad 3^2\equiv9,\quad 4^2\equiv5,\quad 5^2\equiv3\pmod {11}.\) 因此 $5$ 是模 $11$ 的二次剩余，因为 \(4^2\equiv5\pmod {11}.\) 所以 \(\left(\frac5{11}\right)=1.\)
例 2：计算勒让德符号
计算 \(\left(\frac {19}{43}\right).\)
解：
因为 $19\equiv3\pmod4$，$43\equiv3\pmod4$，二者都是 $4k+3$ 型素数，所以二次互反律给出变号： \(\left(\frac {19}{43}\right) =-\left(\frac {43}{19}\right).\) 化简分子： \(43\equiv5\pmod {19},\) 所以 \(\left(\frac {19}{43}\right) =-\left(\frac5{19}\right).\) 再用互反律。因为 $5\equiv1\pmod4$，不变号： \(\left(\frac5{19}\right)=\left(\frac{19}{5}\right).\) 而 \(19\equiv4\pmod5,\) 所以 \(\left(\frac{19}{5}\right)=\left(\frac45\right)=1.\) 因此 \(\left(\frac {19}{43}\right)=-1.\)
例 3：用补充公式
计算 \(\left(\frac {-14}{29}\right).\)
解：
用乘法性： \(\left(\frac {-14}{29}\right) =\left(\frac {-1}{29}\right)\left(\frac2{29}\right)\left(\frac7{29}\right).\)
因为 $29\equiv1\pmod4$， \(\left(\frac {-1}{29}\right)=1.\)
因为 $29\equiv5\pmod8$， \(\left(\frac2{29}\right)=-1.\)
计算 $\left(\frac7{29}\right)$。由于 $7\equiv3\pmod4$，$29\equiv1\pmod4$，翻转不变号： \(\left(\frac7{29}\right)=\left(\frac{29}{7}\right)=\left(\frac1{7}\right)=1.\) 所以 \(\left(\frac {-14}{29}\right)=1\cdot(-1)\cdot1=-1.\)
例 4：雅可比符号不保证有解
计算 $\left(\frac2{15}\right)$，并判断 $x^2\equiv2\pmod {15}$ 是否有解。
解：
因为 $15=3\cdot5$， \(\left(\frac2{15}\right) =\left(\frac2{3}\right)\left(\frac2{5}\right).\) 由 $\left(\frac2p\right)$ 公式： \(3\equiv3\pmod8,\quad \left(\frac2{3}\right)=-1,\) \(5\equiv5\pmod8,\quad \left(\frac2{5}\right)=-1.\) 所以 \(\left(\frac2{15}\right)=1.\)
但看模 $3$： \(x^2\equiv0,1\pmod3,\) 不可能等于 $2$。因此 \(x^2\equiv2\pmod {15}\) 无解。
这说明雅可比符号等于 $1$ 不保证二次同余有解。
例 5：平方和判别
判断 $325$ 能否表示为两个整数平方之和。
解：
分解： \(325=25\cdot13=5^2\cdot13.\) 其中 $5\equiv1\pmod4$，$13\equiv1\pmod4$。没有形如 $4k+3$ 的素因子。因此 $325$ 可以表示为两个平方之和。
实际上 \(325=18^2+1^2=324+1.\)
第五章 原根
本章复习目标
本章研究模 $m$ 的乘法群结构。核心是元素的次数、原根、指数（离散对数）和 $k$ 次剩余。期末中常见考法是“求阶、判原根、用原根解同余”，也可能考离散对数密码体制的基本原理。
本章常考类型：
- 求整数 $a$ 模 $m$ 的次数。
- 判断某个数是否为模 $p$ 的原根。
- 计算或构造原根。
- 用原根把乘法同余转化为指数同余。
- 判断 $k$ 次剩余。
知识点总览
| 小节 | 核心内容 | 复习重点 |
|---|---|---|
| §1 整数的次数 | 最小正整数 $d$ 使 $a^d\equiv1\pmod m$ | 阶整除 $\varphi(m)$ |
| §2 原根 | 阶为 $\varphi(m)$ 的数 | 原根生成缩系 |
| §3 计算次数的方法 | 利用因子试除 | 从 $\varphi(m)$ 的因子中找 |
| §4 计算原根的方法 | 判定阶是否最大 | 检查素因子即可 |
| §5 原根的一个性质 | 原根幂的阶 | $\mathrm{ord}(g^k)=\varphi(m)/(k,\varphi(m))$ |
| §6 指数 | 离散对数 | 把乘法转为加法 |
| §7 一般缩系的构造 | 构造缩系 | 结合中国剩余定理 |
| §8 原根的一个应用 | 用原根解同余 | 常用于幂同余 |
| §9 基于离散对数的公钥密码体制 | Diffie-Hellman/ElGamal 思想 | 正向幂容易，反向离散对数难 |
| §10 $k$ 次剩余 | $x^k\equiv a$ 是否有解 | 转化为指数同余 |
| §11 $k$ 次剩余符号 $\left(\frac np\right)_k$ | 高次剩余的符号 | 理解定义与判别思想 |
按小节详细复习要点
§1 整数的次数。 次数就是元素在模 $m$ 乘法群中的阶。它一定整除 $\varphi(m)$。求阶时不要盲目试所有指数，而应先列出 $\varphi(m)$ 的因子。
§2 原根。 原根是能生成整个缩系的元素。若 $g$ 是模 $m$ 原根，那么每个与 $m$ 互素的剩余类都能唯一写成 $g^r$。不是所有模数都有原根，考试常见的是素数模或小模数。
§3 计算次数的方法。 若已知 $a^{\varphi(m)}\equiv1$，阶只能是 $\varphi(m)$ 的因子。实用方法是从小因子开始试，或不断检查能否把候选阶除以素因子。
§4 计算原根的方法。 对奇素数 $p$，分解 $p-1$，只需检查 $g^{(p-1)/q}\not\equiv1\pmod p$，其中 $q$ 跑遍 $p-1$ 的不同素因子。这个判定比逐个幂列出缩系更快。
§5 原根的一个性质。 若 $g$ 是原根，则 $g^k$ 的阶为 $\varphi(m)/(k,\varphi(m))$。所以原根的所有生成元是 $g^k$，其中 $(k,\varphi(m))=1$。这也说明原根个数为 $\varphi(\varphi(m))$。
§6 指数。 指数就是离散对数。选定原根 $g$ 后，乘法关系变为指数加法： \(\mathrm{ind}_g(ab)\equiv \mathrm{ind}_g a+\mathrm{ind}_g b\pmod{\varphi(m)}.\) 幂关系变为指数乘法： \(\mathrm{ind}_g(a^k)\equiv k\mathrm{ind}_g a\pmod{\varphi(m)}.\)
§7 一般缩系的构造。 若模数可分解为互素部分，可先分别取各模数的缩系，再用孙子定理组合，得到原模数的缩系。这是把复杂模数化为素数幂模数的常用方法。
§8 原根的一个应用。 用原根可把 $x^k\equiv a\pmod p$ 转化为一次同余 $kt\equiv r\pmod {p-1}$。因此高次同余的有解条件、解数都可以用一次同余理论处理。
§9 基于离散对数的公钥密码体制。 离散对数密码的核心是：给定 $g$ 和 $x$，计算 $g^x\bmod p$ 很快；给定 $g$ 和 $g^x$，反求 $x$ 很难。复习时掌握思想即可，通常不要求手工破解大例子。
§10 $k$ 次剩余。 若 $a\equiv g^r\pmod p$，则 $a$ 是 $k$ 次剩余当且仅当 $(k,p-1)\mid r$。若有解，解数为 $(k,p-1)$ 个。
§11 $k$ 次剩余符号 $\left(\frac np\right)_k$。 它是勒让德符号的高次推广，用来描述 $n$ 在模 $p$ 下是否为 $k$ 次幂。复习重点是理解它服务于高次剩余判别，不要把它的计算规则与二次互反律机械混同。
重要定义与定理
整数的次数。 若 $(a,m)=1$，使 \(a^d\equiv1\pmod m\) 成立的最小正整数 $d$ 称为 $a$ 模 $m$ 的次数，记作 \(\mathrm{ord}_m(a)=d.\)
性质：
- 若 $a^k\equiv1\pmod m$，则 $\mathrm{ord}_m(a)\mid k$。
- 由 Euler 定理， \(\mathrm{ord}_m(a)\mid\varphi(m).\)
原根。 若存在 $g$ 满足 \(\mathrm{ord}_m(g)=\varphi(m),\) 则称 $g$ 是模 $m$ 的原根。
若 $g$ 是模 $m$ 的原根，则 \(g^0,g^1,\dots,g^{\varphi(m)-1}\) 构成模 $m$ 的一个缩系。
素数模原根判定。 对奇素数 $p$，若 $p-1$ 的不同素因子为 $q_1,\dots,q_s$，则 $g$ 是模 $p$ 的原根，当且仅当 \(g^{(p-1)/q_i}\not\equiv1\pmod p\) 对每个 $i$ 都成立。
原根幂的阶。 若 $g$ 是模 $m$ 的原根，且 $h=g^k$，则 \(\mathrm{ord}_m(h)=\frac{\varphi(m)}{(k,\varphi(m))}.\) 因此 $g^k$ 也是原根当且仅当 \((k,\varphi(m))=1.\)
指数/离散对数。 若 $g$ 是模 $m$ 的原根，且 $(a,m)=1$，则存在唯一的 $r\pmod{\varphi(m)}$，使 \(g^r\equiv a\pmod m.\) 称 $r$ 为 $a$ 以 $g$ 为底的指数，类似于离散对数。
$k$ 次剩余。 若同余式 \(x^k\equiv a\pmod p\) 有解，则称 $a$ 是模 $p$ 的 $k$ 次剩余。
当 $g$ 是模 $p$ 的原根，设 \(a\equiv g^r\pmod p,\qquad x\equiv g^t\pmod p.\) 则 \(x^k\equiv a\pmod p\) 等价于指数同余 \(kt\equiv r\pmod {p-1}.\) 因此有解当且仅当 \((k,p-1)\mid r.\)
关键证明思路
阶整除指数的证明思路。 设 $d=\mathrm{ord}_m(a)$。若 $a^k\equiv1$，用带余除法写 $k=qd+r$，$0\le r<d$。则 \(1\equiv a^k=(a^d)^qa^r\equiv a^r\pmod m.\) 由 $d$ 的最小性，必须 $r=0$，故 $d\mid k$。
原根判定的证明思路。 若阶不是 $p-1$，则阶是 $p-1$ 的真因子，因此会整除某个 $(p-1)/q_i$。所以只要检查每个素因子 $q_i$ 对应的幂都不是 $1$，就排除所有真因子阶。
$k$ 次剩余判别的证明思路。 原根把模 $p$ 非零剩余类写成 $g^r$，于是乘法问题变成模 $p-1$ 的线性同余 $kt\equiv r$。有解条件就是一次同余的有解条件。
常见题型与解法模板
题型 1：求 $\mathrm{ord}_m(a)$。
- 先确认 $(a,m)=1$。
- 计算 $\varphi(m)$。
- 列出 $\varphi(m)$ 的正因子。
- 从小到大试 $a^d\equiv1\pmod m$。
题型 2：判断 $g$ 是否为模 $p$ 原根。
- 分解 $p-1$。
- 对每个不同素因子 $q\mid p-1$，计算 $g^{(p-1)/q}$。
- 只要有一个结果 $\equiv1\pmod p$，就不是原根。
- 全部不为 $1$，就是原根。
题型 3：解 $x^k\equiv a\pmod p$。
- 找模 $p$ 原根 $g$。
- 写 $a\equiv g^r$，设 $x\equiv g^t$。
- 解线性同余 $kt\equiv r\pmod {p-1}$。
- 把 $t$ 代回 $x\equiv g^t$。
题型 4：离散对数密码体制。
考试通常不要求真正破解，只要理解：
- 已知 $g,a$，计算 $g^a$ 容易。
- 已知 $g,g^a$，求 $a$ 通常困难。
- 安全性来自离散对数问题。
易错点
- 只有 $(a,m)=1$ 时才谈 $\mathrm{ord}_m(a)$。
- 原根不一定对任意模数存在。常见存在情形包括 $2,4,p^k,2p^k$，其中 $p$ 为奇素数。
- 判断模 $p$ 原根时，检查的是 $p-1$ 的不同素因子，不是所有因子。
- 指数是模 $\varphi(m)$ 意义下唯一，不是普通整数唯一。
- $\left(\frac np\right)_k$ 属于高次剩余理论，不要和勒让德符号混淆；二次剩余是 $k=2$ 的特殊情形。
典型例题
例 1：求阶
求 $2$ 模 $9$ 的次数。
解：
因为 $(2,9)=1$，可以谈次数。$\varphi(9)=6$，所以阶整除 $6$。
计算： \(2^1\equiv2\pmod9,\) \(2^2=4\not\equiv1\pmod9,\) \(2^3=8\not\equiv1\pmod9,\) \(2^6=64\equiv1\pmod9.\) 故 \(\mathrm{ord}_9(2)=6.\) 所以 $2$ 是模 $9$ 的原根。
例 2：判断原根
判断 $2$ 是否为模 $11$ 的原根。
解：
因为 $11$ 是素数， \(\varphi(11)=10.\) 分解 \(10=2\cdot5.\) 只需检查 \(2^{10/2}=2^5,\qquad 2^{10/5}=2^2\) 是否为 $1$ 模 $11$。
计算： \(2^5=32\equiv-1\pmod {11},\) \(2^2=4\not\equiv1\pmod {11}.\) 两个都不为 $1$，所以 $2$ 是模 $11$ 的原根。
例 3：由原根求幂的阶
已知 $g$ 是模 $17$ 的原根，求 $g^6$ 模 $17$ 的次数。
解：
因为 $\varphi(17)=16$，且 $g$ 为原根，所以 \(\mathrm{ord}_{17}(g)=16.\) 利用公式： \(\mathrm{ord}_{17}(g^6)=\frac{16}{(6,16)}.\) 由于 \((6,16)=2,\) 故 \(\mathrm{ord}_{17}(g^6)=8.\)
例 4：用原根解高次同余
解 \(x^3\equiv5\pmod {11}.\) 已知 $2$ 是模 $11$ 的原根。
解：
列出 $2$ 的幂： \(2^1\equiv2,\quad 2^2\equiv4,\quad 2^3\equiv8,\quad 2^4\equiv5\pmod {11}.\) 所以 \(5\equiv2^4\pmod {11}.\) 设 \(x\equiv2^t\pmod {11}.\) 则 \(x^3\equiv2^{3t}\equiv2^4\pmod {11}.\) 由于指数模 $10$， \(3t\equiv4\pmod {10}.\) 解这个一次同余。因为 $(3,10)=1$，$3^{-1}\equiv7\pmod {10}$，所以 \(t\equiv4\cdot7=28\equiv8\pmod {10}.\) 因此 \(x\equiv2^8=256\equiv3\pmod {11}.\)
检验： \(3^3=27\equiv5\pmod {11}.\)
例 5：判断 $k$ 次剩余
判断 $3$ 是否为模 $7$ 的三次剩余。
解：
模 $7$ 的一个原根是 $3$，因为 \(3^1=3,\quad 3^2=2,\quad 3^3=6,\quad 3^4=4,\quad 3^5=5,\quad 3^6=1\pmod7.\) 于是 $3\equiv3^1$，即指数 $r=1$。要判断 \(x^3\equiv3\pmod7\) 是否有解，等价于 \(3t\equiv1\pmod6.\) 但 \((3,6)=3\nmid1.\) 所以无解，$3$ 不是模 $7$ 的三次剩余。
第六章 素性判别和整数分解
本章复习目标
本章偏计算数论和密码学应用，研究两个问题：如何判断一个数是不是素数，如何把合数分解。期末通常不会要求大规模计算，但会考算法思想、适用条件和小整数上的手算过程。
本章常考类型：
- 理解算法复杂度和“可计算”的差别。
- 用 Fermat 小定理做素性测试。
- 识别伪素数。
- 用简单方法分解整数，如试除法、Fermat 方法、Kraitchik 思想、$p-1$ 法。
- 比较不同分解方法适合什么类型的数。
知识点总览
| 小节 | 核心内容 | 复习重点 |
|---|---|---|
| §1 关于算法及其计算量 | 算法复杂度 | 多项式时间与指数时间的直观区别 |
| §2 伪素数和素性判别 | Fermat 测试、伪素数 | 通过测试不一定是素数 |
| §3 一些初等的素性判别方法 | 试除、Wilson、Lucas 思想 | 小数可手算，大数要算法 |
| §4 分解整数的费马方法和 Kraitchik 方法 | 平方差分解 | 找 $x^2\equiv y^2\pmod n$ |
| §5 连分数法和二次筛法 | 寻找平方同余 | 理解思想即可 |
| §6 $p-1$ 法 | 利用素因子 $p$ 的 $p-1$ 光滑性 | 适合某个素因子 $p$ 满足 $p-1$ 易分解 |
按小节详细复习要点
§1 关于算法及其计算量。 数论算法的输入长度约为 $\log n$，所以“试到 $\sqrt n$”对大整数是很慢的。复习时要分清：手算小例题可用试除，大整数密码学问题必须考虑算法复杂度。
§2 伪素数和素性判别。 Fermat 小定理给出素数必须满足的同余条件，但合数也可能满足，这就是伪素数。素性测试常能快速证明“合数”，但单一 Fermat 测试不能证明“素数”。
§3 一些初等的素性判别方法。 试除法最朴素；Wilson 定理给出充要条件但计算不实用；基于同余或递推序列的判别法在理论上重要。期末手算题通常只要求试除、Fermat 测试或简单构造。
§4 分解整数的费马方法和 Kraitchik 方法。 Fermat 方法寻找 $n=x^2-y^2$，适合两个因子接近。Kraitchik 方法放宽为寻找非平凡平方同余 $x^2\equiv y^2\pmod n$，再用 gcd 分解。
§5 连分数法和二次筛法。 这两类方法的共同思想是系统寻找许多“接近平方”的数，组合出一个平方同余。二次筛法中会选因子基，把若干关系相乘，使每个素因子的指数变成偶数，从而得到平方。
§6 $p-1$ 法。 $p-1$ 法适合这样的合数 $n$：它有一个素因子 $p$，且 $p-1$ 的素因子都不大。关键不是 $n-1$ 光滑，而是某个未知素因子 $p$ 的 $p-1$ 光滑。
重要定义与定理
算法计算量。 讨论整数算法时，输入规模通常按数字位数或 $\log n$ 计算，而不是按 $n$ 本身计算。试除到 $\sqrt n$ 对小数可行，但对大整数通常不可行。
Fermat 素性测试。 若 $n$ 是素数，且 $(a,n)=1$，则 \(a^{n-1}\equiv1\pmod n.\) 因此若发现 \(a^{n-1}\not\equiv1\pmod n,\) 则 $n$ 一定是合数。
伪素数。 若 $n$ 是合数，但对某个底数 $a$ 满足 \(a^{n-1}\equiv1\pmod n,\) 则称 $n$ 是以 $a$ 为底的 Fermat 伪素数。
Carmichael 数。 合数 $n$ 若对所有 $(a,n)=1$ 的 $a$ 都满足 \(a^{n-1}\equiv1\pmod n,\) 则称 $n$ 为 Carmichael 数。它会骗过所有 Fermat 测试底数。
试除法。 若 $n$ 为合数，则 $n$ 有不超过 $\sqrt n$ 的素因子。因此判断 $n$ 是否素数，只需试除所有不超过 $\sqrt n$ 的素数。
Fermat 分解法。 若奇数 $n$ 可写成 \(n=x^2-y^2=(x-y)(x+y),\) 则得到因子分解。方法是从 \(x=\lceil\sqrt n\rceil\) 开始，依次检查 $x^2-n$ 是否为平方数。适合两个因子比较接近的情况。
Kraitchik 方法。 更一般地，若找到 \(x^2\equiv y^2\pmod n,\) 且 \(x\not\equiv\pm y\pmod n,\) 则 \(n\mid(x-y)(x+y),\) 从而 \((x-y,n),\quad (x+y,n)\) 可能给出 $n$ 的非平凡因子。
$p-1$ 法。 若 $n$ 有素因子 $p$，并且 $p-1$ 的素因子都较小，即 $p-1$ 是“光滑”的，则可取 \(M=\mathrm{lcm}(1,2,\dots,B),\) 使 $p-1\mid M$。若 $(a,p)=1$，则 \(a^M\equiv1\pmod p.\) 因此 \(p\mid a^M-1,\) 计算 \(d=(a^M-1,n)\) 可能得到非平凡因子。
关键证明思路
试除法的证明思路。 若 $n=ab$ 且 $1<a\le b<n$，则 $a^2\le ab=n$，所以 $a\le\sqrt n$。因此合数必有小因子。
Fermat 测试的证明思路。 直接来自费马小定理。它只能给出“若不满足则合数”的充分证据；满足时只能说“可能是素数”。
Kraitchik 方法的证明思路。 从 \(x^2\equiv y^2\pmod n\) 得到 \(n\mid(x-y)(x+y).\) 若 $n$ 不整除 $x-y$ 且不整除 $x+y$，则 $n$ 的素因子被分到两个因子里，取 gcd 可分离出非平凡因子。
$p-1$ 法的证明思路。 对未知素因子 $p$ 使用费马小定理：只要 $p-1\mid M$，就有 $a^M\equiv1\pmod p$，因此 $p$ 会出现在 $(a^M-1,n)$ 中。
常见题型与解法模板
题型 1：试除判素。
- 算 $\sqrt n$。
- 只试除不超过 $\sqrt n$ 的素数。
- 若无因子，则 $n$ 是素数。
题型 2：Fermat 测试。
- 选底数 $a$，通常 $2$ 或小素数。
- 快速幂计算 $a^{n-1}\bmod n$。
- 若不等于 $1$，则 $n$ 为合数。
- 若等于 $1$，只能说通过该底数测试。
题型 3：Fermat 分解。
- 从 $x=\lceil\sqrt n\rceil$ 开始。
- 计算 $x^2-n$。
- 若是平方 $y^2$，则 \(n=(x-y)(x+y).\)
- 否则令 $x=x+1$ 继续。
题型 4：Kraitchik 平方同余。
- 找 $x^2\equiv y^2\pmod n$。
- 检查 $x\not\equiv\pm y\pmod n$。
- 计算 $(x-y,n)$ 或 $(x+y,n)$。
题型 5：$p-1$ 法。
- 选底数 $a$ 和界 $B$。
- 取 $M=\mathrm{lcm}(1,2,\dots,B)$。
- 计算 $d=(a^M-1,n)$。
- 若 $1<d<n$，得到因子；若 $d=1$ 或 $d=n$，换 $a$ 或 $B$。
易错点
- Fermat 测试通过不代表一定是素数。
- Carmichael 数会骗过所有与它互素的 Fermat 底数。
- Fermat 分解适合因子接近的合数；因子差距大时很慢。
- Kraitchik 方法需要非平凡平方同余，若 $x\equiv\pm y\pmod n$ 通常得不到分解。
- $p-1$ 法依赖某个素因子 $p$ 的 $p-1$ 光滑，而不是依赖 $n-1$ 光滑。
典型例题
例 1：试除法判素
判断 $997$ 是否为素数。
解：
因为 \(\sqrt{997}<32.\) 只需试除不超过 $32$ 的素数： \(2,3,5,7,11,13,17,19,23,29,31.\) 逐一检查：
- $997$ 不是偶数。
- 各位数字和为 $25$，不能被 $3$ 整除。
- 末位不是 $0$ 或 $5$。
- $997=7\cdot142+3$。
- $997=11\cdot90+7$。
- $997=13\cdot76+9$。
- $997=17\cdot58+11$。
- $997=19\cdot52+9$。
- $997=23\cdot43+8$。
- $997=29\cdot34+11$。
- $997=31\cdot32+5$。
没有素因子不超过 $\sqrt{997}$，所以 $997$ 是素数。
例 2：Fermat 测试发现合数
用底数 $2$ 判断 $341$ 是否可能为素数。
解：
先分解可知 \(341=11\cdot31,\) 所以它是合数。现在看 Fermat 测试为何可能失败。
计算： \(2^{10}=1024\equiv1\pmod {11},\) 且 \(2^5=32\equiv1\pmod {31}.\) 因此 \(2^{340}=(2^{10})^{34}\equiv1\pmod {11},\) 也有 \(2^{340}=(2^5)^{68}\equiv1\pmod {31}.\) 由中国剩余定理， \(2^{340}\equiv1\pmod {341}.\) 所以 $341$ 是以 $2$ 为底的伪素数。
结论：Fermat 测试底数 $2$ 通过，不能说明 $341$ 是素数。
例 3：Fermat 分解法
用 Fermat 方法分解 $5959$。
解：
先估计： \(77^2=5929<5959<78^2=6084,\) 所以从 $x=78$ 开始。
计算： \(78^2-5959=6084-5959=125,\) 不是平方。
继续： \(79^2-5959=6241-5959=282,\) 不是平方。
\(80^2-5959=6400-5959=441=21^2.\) 于是 \(5959=80^2-21^2=(80-21)(80+21)=59\cdot101.\)
例 4：Kraitchik 方法
设 $n=91$，已知 \(20^2\equiv6^2\pmod {91}.\) 用它分解 $91$。
解：
由 \(20^2\equiv6^2\pmod {91}\) 得 \(91\mid(20-6)(20+6)=14\cdot26.\) 计算 \((20-6,91)=(14,91)=7,\) \((20+6,91)=(26,91)=13.\) 所以 \(91=7\cdot13.\)
例 5：$p-1$ 法
用 $p-1$ 法尝试分解 $n=91$，取 $a=2$，$B=3$。
解：
取 \(M=\mathrm{lcm}(1,2,3)=6.\) 计算 \(2^6-1=64-1=63.\) 于是 \(d=(63,91).\) 因为 \(91=7\cdot13,\qquad 63=7\cdot9,\) 所以 \((63,91)=7.\) 得到非平凡因子 $7$，故 \(91=7\cdot13.\)
这个例子有效，是因为素因子 $7$ 满足 \(7-1=6\) 完全由不超过 $3$ 的素因子构成。
考前速查表
1. 常用符号
| 符号 | 含义 |
|---|---|
| $a\mid b$ | $a$ 整除 $b$ |
| $(a,b)$ | 最大公因数 |
| $[a,b]$ | 最小公倍数 |
| $a\equiv b\pmod m$ | $m\mid a-b$ |
| $\varphi(n)$ | 欧拉函数 |
| $\mu(n)$ | Mobius 函数 |
| $\pi(n)$ | 不超过 $n$ 的素数个数 |
| $\left(\frac ap\right)$ | 勒让德符号，$p$ 为奇素数 |
| $\left(\frac an\right)$ | 雅可比符号，$n$ 为正奇数 |
| $\mathrm{ord}_m(a)$ | $a$ 模 $m$ 的次数 |
2. 高频定理
Bezout 等式。 \((a,b)=d\iff \exists x,y\in\mathbb Z,\ ax+by=d.\)
一次不定方程。 \(ax+by=c\text{ 有整数解}\iff (a,b)\mid c.\)
唯一分解。 \(n=\prod p_i^{\alpha_i}.\) 整除比较指数，gcd 取最小指数，lcm 取最大指数。
一次同余。 \(ax\equiv b\pmod m\text{ 有解}\iff (a,m)\mid b.\)
Euler 定理。 \((a,n)=1\Rightarrow a^{\varphi(n)}\equiv1\pmod n.\)
费马小定理。 \(p\nmid a\Rightarrow a^{p-1}\equiv1\pmod p.\)
Wilson 定理。 \(p\text{ 为素数}\iff (p-1)!\equiv-1\pmod p.\)
欧拉函数。 \(\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).\)
Mobius 反演。 \(F(n)=\sum_{d\mid n}f(d) \Rightarrow f(n)=\sum_{d\mid n}\mu(d)F(n/d).\)
二次互反律。 \(\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.\)
原根判定。 若 $p$ 为奇素数，$p-1$ 的不同素因子为 $q_i$，则 $g$ 是模 $p$ 原根当且仅当 \(g^{(p-1)/q_i}\not\equiv1\pmod p\) 对所有 $q_i$ 成立。
3. 典型解题流程
求 gcd 和 Bezout：
- 辗转相除求 gcd。
- 反代求线性组合。
解 $ax+by=c$：
- 求 $d=(a,b)$。
- 检查 $d\mid c$。
- 求 $ax+by=d$ 的解并乘以 $c/d$。
- 写通解。
解 $ax\equiv b\pmod m$：
- 求 $d=(a,m)$。
- 检查 $d\mid b$。
- 约化为互素情形。
- 求逆元。
- 补齐模 $m$ 下的 $d$ 个解。
中国剩余定理：
- 检查模数两两互素。
- 设 $M=\prod m_i$，$M_i=M/m_i$。
- 求 $M_iN_i\equiv1\pmod {m_i}$。
- 写 $x\equiv\sum a_iM_iN_i\pmod M$。
计算勒让德符号：
- 分子模 $p$ 化简。
- 拆成 $-1$、$2$ 和奇素数因子。
- 用补充公式和互反律。
- 算到分子为小数或 $1$。
判断原根：
- 分解 $p-1$。
- 只检查不同素因子 $q$ 对应的 $g^{(p-1)/q}$。
- 全不为 $1$ 才是原根。
素性判别：
- 小数先试除到 $\sqrt n$。
- 大数可先用 Fermat 测试排除合数。
- 通过 Fermat 测试不等于素数，警惕伪素数。
整数分解：
- 因子接近：优先 Fermat 分解。
- 已有平方同余：用 Kraitchik 的 gcd。
- 某个素因子 $p$ 的 $p-1$ 光滑：尝试 $p-1$ 法。
4. 最后一天复习建议
- 第一遍：看每章“重要定义与定理”，把条件圈出来。
- 第二遍：看“常见题型与解法模板”，每种题至少手算一题。
- 第三遍：重点练二次互反律、一次同余、中国剩余定理、Mobius 反演、原根判定。
- 考场上遇到复杂题，先判断它属于哪类模板：整除、同余、反演、二次剩余、原根、素性判别。