手册 · 第 2 章

数论

质数与因数、最大公因数与最小公倍数、模运算（欧拉定理、费马小定理、中国剩余定理）、不定方程、进制与 p 进赋值。

原书第 33–45 页 · 44 个条目

2.1 质数

在 YouTube 上打开

定义 2.1.1 · 质数

质数是恰好有两个因数的数： $1$ 和它本身。例如， $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$ 都是质数。

注意： $1$ 不是质数， $2$ 是唯一的偶质数。

去学习:定义 21.0.1 · 质数第 21.0 节质数、质因数分解与因数个数

原书第 33 页

注 2.1.2

要判断一个数 $n$ 是不是质数，只需要用小于或等于 $\sqrt{n}$ 的质数去试除。

去学习:注 21.0.2

原书第 33 页已数值验证

概念 2.1.3 · 质因数分解

质因数分解就是把一个数写成若干个质数的乘积。

例： $21$ 的质因数分解是 $3 \times 7$ ， $60$ 的质因数分解是 $2^2 \times 3 \times 5$ 。

去学习:概念 21.0.3 · 质因数分解

原书第 33 页已数值验证

定理 2.1.4 · 一个数的因数个数

如果一个数的质因数分解是

p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k},

那么这个数的因数个数是

(e_1 + 1)(e_2 + 1)\cdots(e_k + 1).

去学习:定理 21.0.4 · 一个数的因数个数

原书第 34 页已数值验证

注 2.1.5

求一个数的因数个数：

求出这个数的质因数分解。
把每个指数加 $1$ 。
把它们乘起来。

去学习:注 21.0.5

原书第 34 页

概念 2.1.6 · 整除判定法则

除数	法则
$2$	个位数字是偶数
$3$	各位数字之和能被 $3$ 整除
$4$	末 $2$ 位能被 $4$ 整除
$5$	个位数字是 $0$ 或 $5$
$6$	能被 $2$ 和 $3$ 整除
$7$	不断减去 $7$ 的倍数，直到剩下一个小数，看它能否被 $7$ 整除
$8$	末 $3$ 位能被 $8$ 整除
$9$	各位数字之和能被 $9$ 整除
$10$	个位数字是 $0$
$11$	把奇数位置上的数字相加（ $O$ ），把偶数位置上的数字相加（ $E$ ）。如果 $\lvert O - E \rvert$ 能被 $11$ 整除，那么这个数也能被 $11$ 整除
$12$	能被 $3$ 和 $4$ 整除
$15$	能被 $3$ 和 $5$ 整除

去学习:概念 22.0.1 · 整除判定法则第 22.0a 节整除判定法则

原书第 34 页已数值验证

概念 2.1.7 · 尾数周期

要求一个很大的幂 $a^b$ 的末一位（或末几位）数字，可以试试找规律：先算出 $a^b$ 的前几个值，就会发现 $b$ 很大时规律在不断重复。

去学习:概念 24.0.4 · 尾数周期第 24.0a 节同余与周期

原书第 35 页

2.2 整数数列

在 YouTube 上打开

2.3 回文数

在 YouTube 上打开

定义 2.3.1

回文数是从前往后读和从后往前读都一样的数，例如 $777$ 、 $383$ 或 $15951$ 。

去学习:定义 28.1.1 · 回文数第 28.1 节回文数

原书第 35 页

2.4 最大公因数与最小公倍数

在 YouTube 上打开

定义 2.4.1 · 最大公因数

两个或多个整数（不全为零）的最大公因数（GCD），是能整除其中每一个数的最大正整数。

注意：它也叫最大公约数（英文也写作 GCF，即 Greatest Common Factor），这两种叫法可以互换。

去学习:定义 23.0.1 · 最大公因数第 23.0a 节用质因数求最大公因数和最小公倍数

原书第 35 页

定义 2.4.2 · 最小公倍数

两个或多个非零整数的最小公倍数（LCM），是能被其中每一个数整除的最小正整数。

更正

原书写的是“两个或多个整数（不全为零）”。只要其中有一个是 $0$ ，就没有正整数能被它整除，所以求最小公倍数要求每个数都不为零。

去学习:定义 23.0.2 · 最小公倍数第 23.0a 节用质因数求最大公因数和最小公倍数

原书第 35 页

概念 2.4.3

在 $m$ 和 $n$ 的质因数分解中，对每个质因数取较低的指数，就得到 $\gcd(m, n)$ 。

在 $m$ 和 $n$ 的质因数分解中，对每个质因数取较高的指数，就得到 $\operatorname{lcm}(m, n)$ 。

去学习:概念 23.0.3 · 用质因数分解求最大公因数和最小公倍数

原书第 36 页已数值验证

定理 2.4.4

两个数的最大公因数与最小公倍数之积，等于这两个数之积：

\gcd(m, n) \cdot \operatorname{lcm}(m, n) = m \cdot n.

去学习:定理 23.0.4 · 最大公因数 × 最小公倍数

原书第 36 页已数值验证

定理 2.4.5

如果两个数有公因数 $c$ ，那么

\gcd(ac, bc) = c \cdot \gcd(a, b).

去学习:定理 23.0.5 · 提取公因数

原书第 36 页已数值验证

定理 2.4.6 · 辗转相除法（欧几里得算法）

辗转相除法说的是

\gcd(x, y) = \gcd(x - ky,\ y)

其中 $x > y$ ， $k$ 是正整数。

去学习:定理 23.0.6 · 辗转相除法第 23.0b 节辗转相除法

原书第 36 页已数值验证

注 2.4.7

我们可以反复使用辗转相除法来求大数的最大公因数：每用一次都得到两个更小的数，直到它们小到可以直接看出最大公因数。例如

\begin{aligned}&\gcd(186, 92) \\ &= \gcd(186 - 2 \cdot 92,\ 92) \\ &= \gcd(2, 92) \\ &= \gcd(2,\ 92 - 2 \cdot 46) \\ &= \gcd(2, 0) = 2.\end{aligned}

去学习:注 23.0.7

原书第 36 页已数值验证

定理 2.4.8 · 裴蜀定理

方程

ax + by = c

有整数解 $x, y$ ，当且仅当 $\gcd(a, b)$ 整除 $c$ 。

去学习:定理 23.0.8 · 裴蜀定理第 23.0c 节裴蜀定理

原书第 37 页已数值验证

2.5 模运算

在 YouTube 上打开

定义 2.5.1

n \equiv a \pmod{b}

表示数 $n$ 和 $a$ 除以 $b$ 的余数相同。

去学习:定义 24.0.1 · 同余第 24.0a 节同余与周期

原书第 37 页

定理 2.5.2

若 $a \equiv x \pmod{n}$ 且 $b \equiv y \pmod{n}$ ，则

ab \equiv xy \pmod{n}.

去学习:定理 24.0.2 · 同余式相乘

原书第 38 页已数值验证

定理 2.5.3

若 $a \equiv x \pmod{n}$ ，则对每个正整数 $m$ ，都有

a^m \equiv x^m \pmod{n}

去学习:定理 24.0.3 · 同余式的乘方

原书第 38 页已数值验证

定理 2.5.4 · 欧拉函数

若 $n$ 的质因数分解是

p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_k^{e_k},

则

\begin{aligned}\varphi(n) = n &\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \\ &\cdots\left(1 - \frac{1}{p_k}\right),\end{aligned}

其中 $\varphi(n)$ 是小于或等于 $n$ 且与 $n$ 互质的正整数的个数。

求一个数的欧拉函数值的步骤：

求出质因数分解。
对每个质数，算出 $1 - \frac{1}{p_i}$ ，并把它们相乘。
再把这个积乘以 $n$ ，就得到欧拉函数值。

去学习:定理 24.0.5 · 欧拉函数第 24.0b 节欧拉定理、费马小定理、威尔逊定理与二项式定理

原书第 38 页已数值验证

定理 2.5.5 · 欧拉定理

a^{\varphi(n)} \equiv 1 \pmod{n}

成立当且仅当

\gcd(a, n) = 1.

去学习:定理 24.0.6 · 欧拉定理

原书第 38 页已数值验证

推论 2.5.6 · 费马小定理

若 $p$ 是质数且 $\gcd(a, p) = 1$ （即 $p \nmid a$ ），则

a^{p-1} \equiv 1 \pmod{p}.

对质数 $p$ ，反过来也成立：只有当 $p \nmid a$ 时才有 $a^{p-1} \equiv 1 \pmod p$ 。注意，这可以由欧拉定理直接得到，因为 $\varphi(p) = p - 1$ 。

更正

原书说 $a^{p-1} \equiv 1 \pmod p$ “当且仅当 $p$ 是质数且 $\gcd(a, n) = 1$ ”。其中的 $n$ 应为 $p$ ，而且这个同余式并不能推出 $p$ 是质数： $2^{340} \equiv 1 \pmod{341}$ ，但 $341 = 11 \cdot 31$ 。定理只是对质数 $p$ 的单向命题。

去学习:推论 24.0.7 · 费马小定理

原书第 39 页已数值验证

事实 2.5.7

对任意整数 $x$ ，

x^2 \equiv 0, 1 \pmod{3}

x^2 \equiv 0, 1 \pmod{4}

去学习:第 26.0 节整数方程的解题策略

原书第 39 页已数值验证

概念 2.5.8

若 $a$ 是 $b \pmod{n}$ 的模逆元，则

ab \equiv 1 \pmod{n}.

由于 $a$ 和 $b$ 互为逆元 $\pmod{n}$ ，我们也记作

a^{-1} \equiv b \pmod{n}

去学习:概念 24.0.8 · 模逆元

原书第 39 页已数值验证

定理 2.5.9 · 威尔逊定理

对质数 $p$ ，

(p-1)! \equiv p - 1 \equiv -1 \pmod{p}.

更正

原书给出这个同余式时没有说明 $p$ 必须是质数。对合数 $p$ 它不成立： $(4-1)! = 6 \equiv 2 \pmod 4$ 。

去学习:定理 24.0.9 · 威尔逊定理

原书第 39 页已数值验证

定理 2.5.10 · 中国剩余定理

若正整数 $x$ 满足

x \equiv a_1 \pmod{n_1}

x \equiv a_2 \pmod{n_2}

\vdots

x \equiv a_k \pmod{n_k}

其中 $n_i$ 两两互质，则 $x$ 有唯一解 $\pmod{n_1 \cdot n_2 \cdot n_3 \cdots n_k}$ 。

去学习:定理 24.0.11 · 中国剩余定理第 24.0c 节中国剩余定理与一次同余式

原书第 40 页已数值验证

注 2.5.11

小心！如果某些 $n_i$ 有公因数，结论可能不成立，因为这些同余式可能互相矛盾。

去学习:注 24.0.12

原书第 40 页

概念 2.5.12 · 解一次同余式

解由 2 个一次同余式组成的方程组，你可以：

尝试检验，直到找到同时满足两个同余式的值；或者
用代数方法：
1. 从 2 个同余式 $n \equiv r_1 \pmod{m_1}$ 和 $n \equiv r_2 \pmod{m_2}$ 出发，其中 $m_1$ 与 $m_2$ 互质。
2. 把它们改写成等式： $n = k m_1 + r_1$ 和 $n = j m_2 + r_2$ 。
3. 让两式模 $m_2$ 相等： $k m_1 + r_1 \equiv r_2 \pmod{m_2}$ ，所以 $k \equiv (r_2 - r_1) \cdot m_1^{-1} \pmod{m_2}$ 。
4. 用尝试检验求出 $m_1^{-1} \pmod{m_2}$ 的值。
5. 利用 $k \equiv k_0 \pmod{m_2}$ ，把它改写成等式： $k = m_2 t + k_0$ 。
6. 把它代回 $n = k m_1 + r_1$ 。
7. 再换回同余式，得到最后的结果 $n \equiv k_0 m_1 + r_1 \pmod{m_1 m_2}$ 。

更正

原书第 3 步写成 $m_1 \equiv (r_2 - r_1) \cdot k^{-1} \pmod{m_2}$ ，第 4 步要求 $k^{-1}$ ；从 $k m_1 + r_1 \equiv r_2$ 解出 $k$ ，应得 $k \equiv (r_2 - r_1) \cdot m_1^{-1}$ 。第 1 步和第 5 步还用了未定义的字母 $b$ 、 $d$ （指 $m_1$ 、 $m_2$ 以及 $k$ 模 $m_2$ 的值）。

去学习:概念 24.0.13 · 解一次同余式

原书第 40 页已数值验证

概念 2.5.13

对互质的 $m_1, m_2$ ，方程组

n \equiv r_1 \pmod{m_1}

n \equiv r_2 \pmod{m_2}

的解是

\begin{aligned}n \equiv{} &r_1 + m_1 (r_2 - r_1) \cdot i \\ &\pmod{m_1 m_2}\end{aligned}

其中 $i \equiv m_1^{-1} \pmod{m_2}$ 。

更正

原书印的是 $n \equiv r_1 + m_1 (r_2 - r_1) \cdot i$ ，没有写模数；解在模 $m_1 m_2$ 下唯一（而且需要 $m_1$ 、 $m_2$ 互质， $m_1^{-1}$ 才存在）。

去学习:概念 24.0.14 · 两个同余式的公式

原书第 41 页已数值验证

注 2.5.14

要解 2 个以上的同余式，就每次合并 2 个，直到只剩 1 个同余式。

去学习:注 24.0.15

原书第 41 页

2.6 不定方程

在 YouTube 上打开

定义 2.6.1

不定方程（丢番图方程）是只关心整数解的多项式方程（整数解指所有未知数都取整数值的解）。

去学习:定义 26.0.1 · 不定方程第 26.0 节整数方程的解题策略

原书第 42 页

概念 2.6.2 · 解不定方程的策略

下面是解不定方程的一些思路。

对不同的数取模。下面两种情况尤其有用：
1. 证明不定方程没有解，或
2. 证明解只能是某种特定形式。
对各项可能的取值估界。当解只有有限个时，这一招通常很管用。
利用代数章节里的各种因式分解公式因式分解，求出所有解。
换元，把不定方程化简。
找出哪些量一定是未知数的倍数或因数，并据此改写不定方程。

去学习:概念 26.0.2 · 解不定方程的策略

原书第 42 页

2.7 进制

在 YouTube 上打开

定义 2.7.1 · 进制

用 $n$ 进制表示一个数，和 $10$ 进制类似，只是不再每满 $10$ 进到下一个位值，而是每满 $n$ 就进一位。

各位数字为 $a_m, a_{m-1}, \ldots, a_2, a_1, a_0$ 的 $n$ 进制数可以写成

\begin{aligned}&a_0 \cdot n^0 + a_1 \cdot n^1 + a_2 \cdot n^2 + \cdots \\ &+ a_{m-1} \cdot n^{m-1} + a_m \cdot n^m\end{aligned}

其中每个 $a_i$ 都是这个数的数字。

去学习:定义 27.0.1 · 进制概念 27.0.2 · $n$ 进制中的位值第 27.0 节任意进制中的位值

原书第 42 页已数值验证

定理 2.7.2 · 麦乐鸡定理

如果 $a$ 和 $b$ 互质，那么不能写成 $a$ 与 $b$ 的非负倍数之和的最大整数是

ab - a - b

对互质的正整数 $a, b$ ，恰好有

\frac{(a-1)(b-1)}{2}

个正整数不能写成 $ma + nb$ 的形式，其中 $m$ 和 $n$ 是非负整数。

更正

原书第二句写的是“其中 $m$ 和 $n$ 是正整数”；个数 $\frac{(a-1)(b-1)}{2}$ 对应的是非负的 $m, n$ 。（取 $a = 3$ ， $b = 5$ ：凑不出的是 $1, 2, 4, 7$ 这 $4$ 个数；若要求 $m, n$ 为正， $3, 5, 6, 9, 10$ 也凑不出。）

去学习:定理 28.2.1 · 麦乐鸡定理第 28.2 节麦乐鸡定理

原书第 43 页已数值验证

注 2.7.3

这个定理适用于“用 $3$ 分和 $5$ 分硬币凑不出的最大金额”这类问题。

去学习:注 28.2.2

原书第 43 页

2.8 p 进赋值

定义 2.8.1

$v_p$ 记号。 $v_p(n)$ 定义为 $n$ 的质因数分解中质数 $p$ 的指数。

例如， $v_5(75) = 2$ ，因为 $75 = 3 \cdot 5^2$ 含有 $2$ 个因数 $5$ ； $v_2(27) = 0$ ，因为 $27$ 是奇数，不含因数 $2$ 。

去学习:第 22.0b 节勒让德公式

原书第 43 页已数值验证

定理 2.8.2 · Vp 乘方公式

v_p(n^k) = k \cdot v_p(n)

说白了： $n^k$ 中 $p$ 的指数，是 $n$ 中 $p$ 的指数的 $k$ 倍。

去学习:第 22.0b 节勒让德公式

原书第 43 页已数值验证

定理 2.8.3 · Vp 乘积公式

v_p(ab) = v_p(a) + v_p(b)

说白了： $ab$ 中 $p$ 的指数 = $a$ 中 $p$ 的指数 + $b$ 中 $p$ 的指数。

去学习:第 22.0b 节勒让德公式

原书第 44 页已数值验证

定理 2.8.4 · Vp 除法公式

v_p\left(\frac{a}{b}\right) = v_p(a) - v_p(b)

说白了： $\frac{a}{b}$ 中 $p$ 的指数 = $a$ 中 $p$ 的指数 − $b$ 中 $p$ 的指数。

去学习:第 22.0b 节勒让德公式

原书第 44 页已数值验证

定理 2.8.5 · Vp 求和公式

若 $v_p(a) \ne v_p(b)$ ，则

v_p(a + b) = \min(v_p(a), v_p(b)).

若 $v_p(a) = v_p(b)$ ，则

v_p(a + b) \ge \min(v_p(a), v_p(b)).

原书第 44 页已数值验证

定理 2.8.6 · 奇质数的升幂定理（LTE）

对奇质数 $p$ ：若

a \equiv b \not\equiv 0 \pmod{p},

则

v_p(a^n - b^n) = v_p(a - b) + v_p(n).

说白了：如果 $a$ 和 $b$ 除以 $p$ 的余数相同，并且这个余数不是 $0$ ，那么 $a^n - b^n$ 中 $p$ 的指数 =（ $a - b$ 中 $p$ 的指数）+（ $n$ 中 $p$ 的指数）。

原书第 44 页已数值验证

注 2.8.7

一定要注意条件 $a \equiv b \not\equiv 0 \pmod p$ ！还要记住， $p = 2$ 不适用这个公式！有时不能直接对指数用升幂定理，这时可以改写含指数的项，再加以应用。

原书第 45 页已数值验证

定理 2.8.8 · 质数 2 的升幂定理（LTE）

对奇数 $a, b$ 和正偶数 $n$ ，

\begin{aligned}&v_2(a^n - b^n) \\ &= v_2(a^2 - b^2) + v_2(n) - 1.\end{aligned}

说白了： $a^n - b^n$ 中 $2$ 的指数 =（ $a^2 - b^2$ 中 $2$ 的指数）+（ $n$ 中 $2$ 的指数）− $1$ 。

（若 $n$ 是奇数，则 $v_2(a^n - b^n) = v_2(a - b)$ 。）

更正

原书给出这个公式时没有任何条件。它要求 $a$ 、 $b$ 为奇数且 $n$ 为偶数：取 $a = 3$ ， $b = 1$ ， $n = 1$ ，公式会给出 $v_2(2) = v_2(8) + 0 - 1 = 2$ ，但 $v_2(2) = 1$ 。原书的文字解释还把“ $n$ 中 $2$ 的指数”写成了“ $n$ 中 $p$ 的指数”。

原书第 45 页已数值验证

定理 2.8.9 · 勒让德定理

v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \cdots

说白了： $n!$ 中因数 $p$ 的个数 = 不超过 $n$ 的 $p$ 的倍数的个数 + 不超过 $n$ 的 $p^2$ 的倍数的个数 + $\cdots$

去学习:定理 22.0.2 · 勒让德定理第 22.0b 节勒让德公式

原书第 45 页已数值验证