Appearance
整除与同余基础（Divisibility & Congruence）
核心定位
整除与同余是初等数论的基石。整除理论研究整数的可除性质与因式分解，同余理论则将整数关系转化为「模运算」，极大简化了复杂计算。本笔记从整除的基本性质出发，逐步建立带余除法、裴蜀定理、算术基本定理、同余方程、中国剩余定理与费马小定理的完整知识体系，与 数学归纳法、求和式的计算方式 等方法论工具紧密关联。
一、整除的基本性质
1.1 整除的定义
整除（Divisibility）
设 $a, b \in \mathbb{Z}$，$b \neq 0$。若存在整数 $q$使得$a = bq$，则称 $b$整除$a$，记作 $b \mid a$；否则称 $b$不整除$a$，记作 $b \nmid a$。此时 $b$称为$a$ 的因数（或约数），$a$称为$b$ 的倍数。
1.2 整除的基本性质
核心传递性质
- 传递性：若 $a \mid b$且$b \mid c$，则 $a \mid c$。
- 线性组合：若 $a \mid b$且$a \mid c$，则对任意整数 $x, y$，有 $a \mid (bx + cy)$。
- 倍数关系：若 $a \mid b$且$b \mid a$，则 $a = \pm b$。
- 单位因子：$\pm 1$ 整除任何整数。
- 零的特例：任何非零整数整除 $0$，但 $0$ 不整除任何非零整数。
证明（线性组合）：由 $a \mid b$知$b = aq_1$，由 $a \mid c$知$c = aq_2$，则 $bx + cy = a(q_1x + q_2y)$，故 $a \mid (bx + cy)$。特别地，取 $x = y = 1$得$a \mid (b + c)$；取 $x = 1, y = -1$得$a \mid (b - c)$。
二、带余除法
带余除法（Division Algorithm）
设 $a, b \in \mathbb{Z}$，$b \neq 0$，则存在唯一的整数 $q$（商）和 $r$（余数）满足： $$a = bq + r, \quad 0 \le r < |b|$$ 当 $r = 0$时，即$b \mid a$。
唯一性证明思路
若存在两组 $(q_1, r_1)$和$(q_2, r_2)$满足条件，则$b(q_1 - q_2) = r_2 - r_1$。由于 $|r_2 - r_1| < |b|$，必有 $q_1 = q_2$且$r_1 = r_2$。
三、最大公约数与欧几里得算法
3.1 最大公约数（GCD）
定义
设 $a, b$ 不全为零，$d$是$a$与$b$的最大公约数，记作$d = \gcd(a, b)$，当且仅当：
- $d \mid a$且$d \mid b$（公因子）
- 若 $c \mid a$且$c \mid b$，则 $c \mid d$（最大性）
3.2 最小公倍数（LCM）
$\operatorname{lcm}(a, b)$是$a$与$b$ 的最小的正公倍数。重要关系： $$\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |ab|$$
3.3 欧几里得算法（辗转相除法）
$$\gcd(a, b) = \gcd(b, a \bmod b)$$
反复应用带余除法，直到余数为 $0$，此时非零除数即为最大公约数。
示例：求 $\gcd(252, 105)$： $$ \begin{aligned} 252 &= 105 \times 2 + 42 \newline 105 &= 42 \times 2 + 21 \newline 42 &= 21 \times 2 + 0 \end{aligned} $$ 故 $\gcd(252, 105) = 21$。
四、裴蜀定理（Bézout's Lemma）
裴蜀定理
设 $a, b$不全为零，则存在整数$x, y$ 使得： $$ax + by = \gcd(a, b)$$ 且 $\gcd(a, b)$是$ax + by$ 能表示的最小的正整数。
4.1 扩展欧几里得算法
通过反向代入辗转相除的过程求出系数 $x, y$。仍以 $252$和$105$ 为例：
由 $21 = 105 - 42 \times 2$，且 $42 = 252 - 105 \times 2$，代入： $$21 = 105 - (252 - 105 \times 2) \times 2 = 105 \times 5 - 252 \times 2$$ 得 $x = -2, y = 5$。
应用场景
裴蜀定理是解一次不定方程 $ax + by = c$的理论基础——该方程有整数解当且仅当$\gcd(a, b) \mid c$。详见 不定方程与丢番图方程。
五、算术基本定理
算术基本定理（Fundamental Theorem of Arithmetic）
任一大于 $1$的整数$n$ 都可以唯一地分解为素数的乘积（不计顺序）： $$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$ 其中 $p_1 < p_2 < \cdots < p_k$ 为素数，$\alpha_i \ge 1$。
依据唯一分解，$\gcd(a, b)$和$\operatorname{lcm}(a, b)$可以通过指数取$\min$和$\max$ 分别计算。
六、同余的基本概念与性质
6.1 同余的定义
同余（Congruence）
设 $m > 0$。若 $m \mid (a - b)$，则称 $a$与$b$模$m$同余，记作$a \equiv b \pmod m$。
6.2 同余的基本运算性质
若 $a \equiv b \pmod m$且$c \equiv d \pmod m$，则：
- 加减：$a \pm c \equiv b \pm d \pmod m$
- 乘法：$ac \equiv bd \pmod m$
- 幂运算：$a^n \equiv b^n \pmod m$
注意
同余的除法不总是成立。仅当 $\gcd(c, m) = 1$时，从$ac \equiv bc \pmod m$才能推出$a \equiv b \pmod m$。
七、一次同余方程
一次同余方程 $ax \equiv b \pmod m$
设 $d = \gcd(a, m)$：
- 若 $d \nmid b$，则无解。
- 若 $d \mid b$，则在模 $m$意义下恰有$d$ 个解。
当 $d = 1$时，解为$x \equiv a^{-1}b \pmod m$，其中 $a^{-1}$是$a$模$m$ 的乘法逆元（由扩展欧几里得算法求出）。
八、中国剩余定理（CRT）
中国剩余定理
设 $m_1, m_2, \dots, m_k$ 两两互素，$m = m_1 m_2 \cdots m_k$，则同余方程组： $$\begin{cases} x \equiv a_1 \pmod{m_1} \newline x \equiv a_2 \pmod{m_2} \newline \quad \vdots \newline x \equiv a_k \pmod{m_k} \end{cases}$$ 在模 $m$ 下有唯一解： $$x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod m$$ 其中 $M_i = m / m_i$，$y_i$满足$M_i y_i \equiv 1 \pmod{m_i}$（即 $M_i$模$m_i$ 的逆元）。
证明思路：令 $M_i = m/m_i$，则对 $j \neq i$有$M_i \equiv 0 \pmod{m_j}$；又 $M_i y_i \equiv 1 \pmod{m_i}$，故 $a_i M_i y_i \equiv a_i \pmod{m_i}$且对其余模为$0$，求和即得解。唯一性由模两两互素保证。
CRT 的威力
CRT 将大模数问题分解为小模数问题，是数论中最强大的工具之一。即使模不互素，也可通过逐步合并方程组来处理。
九、费马小定理
费马小定理（Fermat's Little Theorem）
设 $p$ 为素数，$a$为不被$p$ 整除的整数，则： $$a^{p-1} \equiv 1 \pmod p$$
证明：考虑集合 $\lbrace a, 2a, 3a, \dots, (p-1)a\rbrace $模$p$。由于 $\gcd(a, p) = 1$，该集合模 $p$恰为$\lbrace 1, 2, \dots, p-1\rbrace $ 的一个排列。将它们相乘： $$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p$$ 由 $\gcd((p-1)!, p) = 1$，两边约去 $(p-1)!$即得$a^{p-1} \equiv 1 \pmod p$。
逆元应用：由费马小定理，$a \cdot a^{p-2} \equiv 1 \pmod p$，故 $a^{p-2}$是$a$模素数$p$ 的逆元。这在模素数下求逆比扩展欧几里得更快捷。
十、威尔逊定理
威尔逊定理（Wilson's Theorem）
$(p-1)! \equiv -1 \pmod p$当且仅当$p$ 为素数。
充分性证明（$p$素数时）：对每个$a \in \lbrace 2, 3, \dots, p-2\rbrace $，其模 $p$的逆元$a^{-1}$也在此范围内且$a \neq a^{-1}$（因为 $a^2 \equiv 1 \pmod p$仅有解$a \equiv \pm 1$）。故 $\lbrace 2, \dots, p-2\rbrace $中的数可两两配对，乘积为$1$。因此 $(p-1)! \equiv 1 \cdot (p-1) \equiv -1 \pmod p$。
必要性：若 $p$为合数，则存在$d \mid p$且$1 < d < p$，从而 $d \mid (p-1)!$，故 $(p-1)! \not\equiv -1 \pmod p$。
十一、典型例题
例 1：整除性质
证明：若 $n$为奇数，则$8 \mid (n^2 - 1)$。
解：设 $n = 2k + 1$，则 $n^2 - 1 = 4k(k+1)$。$k$与$k+1$中必有一个偶数，故$k(k+1)$ 为偶数，$4k(k+1)$被$8$ 整除。
例 2：裴蜀定理
求整数 $x, y$使得$37x + 23y = 1$。
解：用扩展欧几里得算法： $$\begin{aligned} 37 &= 23 \times 1 + 14 \newline 23 &= 14 \times 1 + 9 \newline 14 &= 9 \times 1 + 5 \newline 9 &= 5 \times 1 + 4 \newline 5 &= 4 \times 1 + 1 \newline 4 &= 1 \times 4 + 0 \end{aligned}$$ 回代得 $1 = 5 - 4 \times 1 = \cdots = 37 \times 5 + 23 \times (-8)$，即 $x = 5, y = -8$。
例 3：中国剩余定理
解同余方程组：$x \equiv 2 \pmod 3,\thickspace x \equiv 3 \pmod 5,\thickspace x \equiv 2 \pmod 7$。
解：$m = 105$，$M_1 = 35$，$M_2 = 21$，$M_3 = 15$。求逆：$35 \times 2 \equiv 1 \pmod 3$，$21 \times 1 \equiv 1 \pmod 5$，$15 \times 1 \equiv 1 \pmod 7$。故 $$x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \equiv 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$$
例 4：费马小定理求逆元
求 $3$在模$7$ 下的乘法逆元。
解：由费马小定理，$3^{6} \equiv 1 \pmod 7$，故 $3^{-1} \equiv 3^5 \pmod 7$。计算：$3^2 = 9 \equiv 2$，$3^4 \equiv 2^2 = 4$，$3^5 \equiv 3^4 \cdot 3 \equiv 4 \cdot 3 = 12 \equiv 5 \pmod 7$。验证：$3 \times 5 = 15 \equiv 1 \pmod 7$。
例 5：威尔逊定理的应用
求 $15! \bmod 17$。
解：由威尔逊定理，$16! \equiv -1 \pmod{17}$。而 $16! = 16 \times 15! \equiv (-1) \times 15! \pmod{17}$。故 $(-1) \times 15! \equiv -1 \pmod{17}$，乘以 $-1$得$15! \equiv 1 \pmod{17}$。验算：$15! = 1307674368000$，除以 $17$确实余$1$。
例 6：同余方程
解 $6x \equiv 9 \pmod{15}$。
解：$d = \gcd(6, 15) = 3$，且 $3 \mid 9$，故有 $3$个解。先除以$3$：$2x \equiv 3 \pmod 5$。在模 $5$下$2^{-1} \equiv 3$，故 $x \equiv 3 \times 3 = 9 \equiv 4 \pmod 5$。回到模 $15$：$x \equiv 4, 9, 14 \pmod{15}$。
十二、Lifting the Exponent 引理（LTE）
LTE 引理——指数提升引理
设 $p$ 为奇素数，$a, b$ 为整数，$n$为正整数，且$p \mid a - b$但$p \nmid a, p \nmid b$，则： $$v_p(a^n - b^n) = v_p(a - b) + v_p(n)$$ 其中 $v_p(m)$表示$p$在$m$中的素数幂次（即$p^{v_p(m)} \mid m$但$p^{v_p(m)+1} \nmid m$）。
$p = 2$的情形（需额外条件）：若$2 \mid a - b$且$a, b$ 均为奇数，则：
- 当 $n$ 为偶数时：$v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1$
- 当 $n$ 为奇数时：$v_2(a^n - b^n) = v_2(a - b)$
LTE 引理（和的形式）
设 $p = 2$，$a, b$ 均为奇数，$n$为偶数，则$v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1$。 设 $p$为奇素数或$p = 2$且$n$ 为奇数，$p \mid a + b$，$p \nmid a, p \nmid b$，则 $v_p(a^n + b^n) = v_p(a + b) + v_p(n)$（要求 $n$ 为奇数）。
证明思路（核心情形）：写 $a = b + kp$（$v_p(k) = v_p(a-b) - 1$），用二项式展开： $$a^n - b^n = (b + kp)^n - b^n = \sum_{i=1}^{n} \binom{n}{i} b^{n-i} (kp)^i$$ 分析每一项的 $p$-adic 赋值，主项 $i=1$给出$v_p(nbkp) = v_p(n) + v_p(a-b)$，其余项被 $p$ 整除更高次。
竞赛应用
LTE 是处理幂差 $a^n - b^n$的$p$-adic 赋值的神器。在证明整除性、求解不定方程时极有用，特别是处理 $a^n \equiv b^n \pmod{p^k}$ 型问题。
LTE 应用 1
求 $v_3(7^{100} - 1)$。
解：$7 - 1 = 6$，$v_3(6) = 1$。由 LTE，$v_3(7^{100} - 1^{100}) = v_3(7 - 1) + v_3(100) = 1 + 0 = 1$。即 $3 \mid 7^{100} - 1$，但 $9 \nmid 7^{100} - 1$。
LTE 应用 2
证明：$2^{n+1} \nmid 3^{2^n} - 1$对任意$n \ge 1$ 成立。
证：$v_2(3^{2^n} - 1) = v_2(3 - 1) + v_2(3 + 1) + v_2(2^n) - 1 = 1 + 2 + n - 1 = n + 2$。故 $2^{n+2} \mid 3^{2^n} - 1$但$2^{n+3} \nmid 3^{2^n} - 1$，特别地 $2^{n+1} \mid 3^{2^n} - 1$。所以原命题错误，正确结论是 $2^{n+2} \mid 3^{2^n} - 1$。
十三、高斯引理（Gauss's Lemma）
高斯引理
设 $p$ 为奇素数，$\gcd(a, p) = 1$。考虑 $a, 2a, 3a, \dots, \frac{p-1}{2} \cdot a$的最小正剩余（模$p$），若其中有 $k$个大于$\frac{p-1}{2}$，则： $$\left(\frac{a}{p}\right) = (-1)^k$$
证明概要：设 $r_1, r_2, \dots, r_s$是模$p$后$\le (p-1)/2$ 的部分，$q_1, q_2, \dots, q_t$是$> (p-1)/2$ 的部分（$s + t = (p-1)/2$）。则 $\lbrace r_1, \dots, r_s, p - q_1, \dots, p - q_t\rbrace $是$1, 2, \dots, (p-1)/2$ 的一个排列（需证这些数两两不同）。于是： $$a \cdot 2a \cdots \tfrac{p-1}{2} a \equiv (-1)^t \cdot 1 \cdot 2 \cdots \tfrac{p-1}{2} \pmod p$$ 即 $a^{(p-1)/2} \equiv (-1)^t \pmod p$，结合欧拉判别法得 $\left(\frac{a}{p}\right) = (-1)^t = (-1)^k$。
高斯引理的推论：$\left(\frac{2}{p}\right)$ 公式
$$\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases}1 & p \equiv \pm 1 \pmod 8 \newline -1 & p \equiv \pm 3 \pmod 8\end{cases}$$
证明：取 $a = 2$，则 $2, 4, 6, \dots, p-1$中超过$(p-1)/2$的个数$k$等于$\lfloor p/4 \rfloor$或类似值，分类讨论$p \bmod 8$ 得上述公式。
十四、素数判定的初等方法
Wilson 判定（充要条件）
$n > 1$为素数$\iff (n-1)! \equiv -1 \pmod n$。
Fermat 反向判定的反例
若 $a^{n-1} \equiv 1 \pmod n$，并不能推出 $n$为素数。这种合数$n$称为以$a$ 为底的伪素数。
- 对所有 $a$（$\gcd(a,n)=1$）都满足 $a^{n-1} \equiv 1 \pmod n$的合数称为 Carmichael 数，最小的是$561 = 3 \cdot 11 \cdot 17$。
Miller–Rabin 判定
若 $n$为素数，写$n - 1 = 2^s \cdot d$（$d$为奇数），则对任意$\gcd(a, n) = 1$，要么 $a^d \equiv 1 \pmod n$，要么存在 $0 \le r < s$使$a^{2^r d} \equiv -1 \pmod n$。不满足该条件的 $n$ 必为合数。
实战
Miller–Rabin 是竞赛/工业中常用的快速素性测试。对 $n < 3,317,044,064,679,887,385,961,981$，只需测试 $a \in \lbrace 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\rbrace $ 即可。
十五、整除判别法系统表
| 除数 | 判别法 |
|---|---|
| $2$ | 末位为偶数 |
| $3$ | 数字和被$3$ 整除 |
| $4$ | 末两位被$4$ 整除 |
| $5$ | 末位为$0$或$5$ |
| $7$ | 截末位乘$2$ 减去剩余部分，反复 |
| $8$ | 末三位被$8$ 整除 |
| $9$ | 数字和被$9$ 整除 |
| $11$ | 奇位数字和与偶位数字和之差被$11$ 整除 |
| $13$ | 截末位乘$4$ 加剩余部分，反复 |
$p$-adic 截断判别：设 $10^k \equiv 1 \pmod p$（$k = \operatorname{ord}_p(10)$），则 $p \mid n$等价于将$n$按$k$位分段求和后被$p$ 整除。
十六、阶与原根的初步应用（详尽版见 二次剩余与阶）
阶对乘法结构的应用
设 $\gcd(a, m) = 1$，$d = \operatorname{ord}_m(a)$，则：
- $a^0, a^1, \dots, a^{d-1}$模$m$ 两两不同余
- $a^i \equiv a^j \pmod m \iff d \mid (i - j)$
- $1, a, a^2, \dots, a^{d-1}$构成$\lbrace x : x^d \equiv 1 \pmod m\rbrace $的全部解（当$m$ 为素数时）
阶的应用
设 $p$ 为素数，$a \not\equiv 0 \pmod p$。证明：$\sum_{k=0}^{p-2} a^k \equiv 0 \pmod p$当且仅当$a \not\equiv 1 \pmod p$。
证：若 $a \equiv 1$，则和为 $p - 1 \not\equiv 0 \pmod p$。若 $a \not\equiv 1$，由等比求和 $\sum_{k=0}^{p-2} a^k = \frac{a^{p-1} - 1}{a - 1}$，由费马小定理 $a^{p-1} \equiv 1$，分子为 $0$，分母 $\not\equiv 0$，故和为 $0$。
十七、组合数的整除性
Kummer 定理（库默尔）
$p$素数，则$v_p\binom{m+n}{m}$等于$m$与$n$在$p$ 进制下相加时进位的次数。
等价表述：$\binom{m+n}{m}$中$p$的幂次等于$m, n$在$p$-进制加法中的进位次数。
由此推论
$p \mid \binom{p}{k}$对所有$1 \le k \le p-1$ 成立（$p$ 素数）。
与 Lucas 定理的关系
Lucas 定理（详见 组合数论）刻画 $\binom{m+n}{m} \bmod p$，而 Kummer 刻画其 $p$-adic 赋值，两者从不同角度描述组合数的整除性。
十八、欧拉降幂与广义降幂
广义欧拉降幂
对任意 $a, b \ge 0$和$m \ge 1$： $$a^b \equiv \begin{cases} a^{b \bmod \varphi(m)} \pmod m & \gcd(a, m) = 1 \newline a^b & b < \varphi(m) \newline a^{(b \bmod \varphi(m)) + \varphi(m)} \pmod m & \text{否则} \end{cases}$$
嵌套幂次
求 $2^{3^{4^{5}}} \bmod{100}$。
解：$\varphi(100) = 40$，$\gcd(2, 100) = 2 \neq 1$，需用广义降幂。先计算 $3^{4^5} \bmod 40$。$\varphi(40) = 16$，$\gcd(3, 40) = 1$，故 $3^{4^5} \equiv 3^{4^5 \bmod 16} \pmod{40}$。$4^5 = 1024$，$1024 \bmod 16 = 0$，故 $3^{4^5} \equiv 3^0 = 1 \pmod{40}$。但 $3^{4^5} > \varphi(100) = 40$，故 $2^{3^{4^5}} \equiv 2^{1 + 40} = 2^{41} \pmod{100}$。$2^{41} = 2 \cdot (2^{10})^4 = 2 \cdot 1024^4 \equiv 2 \cdot 24^4 \pmod{100}$，$24^2 = 576 \equiv 76$，$24^4 \equiv 76^2 = 5776 \equiv 76$，故 $2^{41} \equiv 2 \cdot 76 = 152 \equiv 52 \pmod{100}$。
十九、典型例题（进阶）
例 7：Lifting the Exponent
证明 $v_2(3^n - 1) = \begin{cases} 1, & n \text{ 奇} \newline 2 + v_2(n), & n \text{ 偶}\end{cases}$。
证：$n$奇时$v_2(3^n - 1) = v_2(3 - 1) = 1$（LTE 和形式：$v_2(a^n - b^n) = v_2(a-b)$）。$n$偶时$v_2(3^n - 1^n) = v_2(3 - 1) + v_2(3 + 1) + v_2(n) - 1 = 1 + 2 + v_2(n) - 1 = 2 + v_2(n)$。
例 8：高斯引理应用
求 $\left(\frac{5}{13}\right)$ 的值。
解：$a = 5$，$p = 13$，$(p-1)/2 = 6$。考虑 $5, 10, 15, 20, 25, 30$模$13$ 的最小正剩余：$5, 10, 2, 7, 12, 4$。其中 $> 6$的有$10, 7, 12$共$3$ 个，$k = 3$为奇数，故$\left(\frac{5}{13}\right) = (-1)^3 = -1$。验证：$13 \equiv \pm 3 \pmod 5$？$13 \equiv 3 \pmod 5$，而 $3$是$5$的非剩余（因$1^2 = 1, 2^2 = 4$），故 $\left(\frac{13}{5}\right) = \left(\frac{3}{5}\right) = -1$。又 $5 \equiv 1 \pmod 4$，二次互反律给 $\left(\frac{5}{13}\right) = \left(\frac{13}{5}\right) = -1$。✓
例 9：组合数整除
求 $v_3\binom{100}{50}$。
解（Kummer）：$50 = 1212_3 = 1 \cdot 27 + 2 \cdot 9 + 1 \cdot 3 + 2 = 1212_3$，验算 $27 + 18 + 3 + 2 = 50$ ✓。$50 + 50 = 100 = 10201_3 = 81 + 0 + 2 \cdot 9 + 0 + 1 = 81 + 18 + 1 = 100$ ✓。$50 + 50$在$3$ 进制下加法：$1212 + 1212 = 10201$，进位过程：个位 $2+2=4=3+1$，进 $1$；十位 $1+1+1=3=3+0$，进 $1$；百位 $2+2+1=5=3+2$，进 $1$；千位 $1+1+1=3=3+0$，进 $1$。共 $4$次进位。故$v_3 \binom{100}{50} = 4$。
例 10：整除判别法
判断 $7$是否整除$259{,}308{,}325$。
解（截末位法）：$259308325 \to 25930832 - 5 \cdot 2 = 25930822 \to 2593082 - 2 \cdot 2 = 2593078 \to 259307 - 8 \cdot 2 = 259291 \to 25929 - 1 \cdot 2 = 25927 \to 2592 - 7 \cdot 2 = 2578 \to 257 - 8 \cdot 2 = 241 \to 24 - 1 \cdot 2 = 22$，$7 \nmid 22$。故 $7 \nmid 259308325$。
二十、知识链接
- 数学归纳法 — 整除性质的归纳证明（如 $8 \mid (3^{2n} - 1)$）
- 求和式的计算方式 — 利用同余化简求和取模问题
- 不定方程与丢番图方程 — 裴蜀定理的直接应用
- 数论函数与欧拉定理 — 费马小定理的推广形式
- 二次剩余与阶 — 同余方程向二次与高阶的延伸