Elementary Number Theory

1. 素数和最大公因子
2. Congruences
3. 特殊的同余式
4. 乘性函数
- 4.1. 欧拉 $φ$ 函数
- 4.2. 因子和函数、因子个数函数
5. Primitive Roots
6. Quadratic Residues
7. Modular Square Roots
- 7.1. 求模为素数时的平方根
- 7.2. 求模为合数时的平方根
  - 7.2.1. 已知合数分解
  - 7.2.2. 未知合数分解
8. 参考

1. 素数和最大公因子

1.1. 素数

定义：素数是大于 $1$ 的正整数，并且除了 $1$ 和它本身不能被其他正整数所整除。例如整数 $2, 3, 5, 13, 101$ 和 $163$ 等都是素数。

1.2. 算术基本定理（The Fundamental Theorem of Arithmetic）

算术基本定理是一个重要的结果，它说明素数是整数的乘法构成单元。

定理（算术基本定理）：每个大于 $1$ 的正整数都可以被唯一地写成素数的乘积，在乘积中的素因子按照非降序排列。

有时算术基本定理被扩展应用到整数 1, 即 1 被看作是唯一地被写成素数的空乘积，

例题：一些正整数的分解如下： $\begin{aligned} 240 & = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 = 2^{4} \cdot 3 \cdot 5 \\ 289 & = 17 \cdot 17 = 17^{2} \\ 1001 & = 7 \cdot 11 \cdot 13 \end{aligned}$

整数分解中把素因子组合成幂的形式被称为素幂分解（prime-power factorization）。

1.3. 最大公因子

定义（最大公因子）：两个不同时为零的整数 $a, b$ 的最大公因子就是指能同时整除 $a, b$ 的最大的整数。 $a, b$ 的最大公因子记为 $(a, b)$ ，或者记为 $gcd (a, b)$ 。

定义（互素）：如果两个整数 $a, b$ 的最大公因子 $gcd (a, b) = 1$ ，那么这两个数就被称为互素的。

1.4. 欧几里得算法

欧几里得算法（Euclidean Algorithm）是一种快速寻找最大公因子的算法。

定理（欧几里得算法）：整数 $a \geq b > 0$ ，令 $r_{0} = a, r_{1} = b$ 。如果我们做带余除法得到 $r_{j} = r_{j + 1} q_{j + 1} + r_{j + 2}$ ，且 $0 < r_{j + 2} < r_{j + 1}, j = 0, 1, 2, n - 2$ ，且有 $r_{n + 1} = 0$ ，那么 $gcd (a, b) = r_{n}$ ，即最后一个非零余数。

从定理中我们看到通过带余除法，在每一步中被除数和除数被更小的数代替，这些更小的数实际上是每一步中的除数和余数，运算直到余数为零时终止，这一系列的运算产生了一系列的等式，而最大公因子就是最后一个非零的余数。

例题：求 $gcd (252, 198)$ 。利用欧几里得算法，其步骤如下： $\begin{aligned} 252 & = 1 \cdot 198 + 54 \\ 198 & = 3 \cdot 54 + 36 \\ 54 & = 1 \cdot 36 + 18 \\ 36 & = 2 \cdot 18 \end{aligned}$ 我们将这些步骤总结在下表中：

$j$	$r_{j}$	$r_{j + 1}$	$q_{j + 1}$	$r_{j + 2}$
0	252	198	1	54
1	198	54	3	36
2	54	36	1	18
3	36	18	2	0

最后一个非零余数（在最后一列倒数第二行的那个数）就是 252 和 198 的最大公因子，因此 $gcd (252, 198) = 18$ 。

1.5. 线性丢番图方程

考虑下面的问题：一个人想购买 510 美元的旅游支票，支票只有 20 美元和 50 美元两种，那么每一种应该买多少？如果我们令 $x$ 表示他应该买的 20 美元支票的数量， $y$ 表示 50 美元支票的数量，那么就应满足方程 $20 x + 50 y = 510$ 。为了解决这一问题，我们应该求出这个方程的所有解，其中 $x, y$ 为非负整数。

类似的问题有，当一个妇女想邮寄一个包裹。邮局的职员测定邮寄这个包裹的费用是 83 美分，但是只有 6 美分和 15 美分的邮票，那么是否有这两种邮票的组合后的面值恰好可以来邮寄这个包裹呢？为了回答这个问题，我们先令 $x$ 表示 6 美分邮票的数量，令 $y$ 表示 15 美分邮票的数量，那么有 $6 x + 15 y = 83$ ，其中 $x, y$ 是非负整数。

当我们需要求解特定方程的整数解的时候，那么就得到了一个丢番图方程，这些方程是根据古希腊数学家丢番图（Diophantus）而命名的，他写下了一些方程并将解限定在有理数域上。 方程 $a x + b y = c$ ，其中 $a, b, c$ 是整数，被称为关于两个变量的线性丢番图方程。

定理：设 $a, b$ 是整数且 $d = gcd (a, b)$ 。如果 $d ∤ c$ ，那么方程 $a x + b y = c$ 没有整数解。如果 $d ∣ c$ ，那么存在无穷多个整数解。另外，如果 $x = x_{0}, y = y_{0}$ 是方程的一个特解，那么所有的解可以表示为 $x = x_{0} + (b / d) n, y = y_{0} - (a / d) n$ 其中 $n$ 是整数。

例题：求线性丢番图方程 $15 x + 6 y = 7$ 的解。因为 $gcd (15, 6) = 3$ ，但是 $3 ∤ 7$ 。所以根据上面定理，这个线性丢番图方程没有整数解。

例题：求线性丢番图方程 $21 x + 14 y = 70$ 的解。因为 $gcd (21, 14) = 7$ ，而且 $7 ∣ 70$ 。所以根据上面定理，这个线性丢番图方程存在无穷多个整数解。容易知道 $x_{0} = 10, y_{0} = - 10$ 是方程的一个特解。根据上面定理，这个线性丢番图方程的所有解为 $x = 10 + (14 / 7) n, y = - 10 - (21 / 7) n$ ，其中 $n$ 是整数。

2. Congruences

2.1. 同余定义

定义： 若 $a$ 和 $b$ 是整数，且 $m ∣ (a - b)$ ，则称 $a$ 和 $b$ 模 $m$ 同余。 若 $a$ 和 $b$ 模 $m$ 同余，则记 $a \equiv b (\mod m)$ 。若 $m ∤ (a - b)$ ，则记 $a ≢ b (\mod m)$ ，并称 $a$ 模 $m$ 不同余于 $b$ 。

例题：因为 $9 ∣ (22 - 4)$ ，所以 $22 = 4 (\mod 9)$ 。另外，因为 $9 ∤ (13 - 5)$ ，所以 $13 ≢ 5 (\mod 9)$ 。

2.2. 同余相关定理

定理：设 $m$ 是正整数。模 $m$ 的同余满足下面的性质：

自反性（Reflexive Property）。若 $a$ 是整数，则 $a \equiv a (\mod m)$ ；
对称性（Symmetric Property）。若 $a$ 和 $b$ 是整数，且 $a \equiv b (\mod m)$ ，则 $b \equiv a (\mod m)$ ；
传递性（Transitive Property）。若 $a, b$ 和 $c$ 是整数，且 $a \equiv b (\mod m)$ 和 $b \equiv c (\mod m)$ ，则 $a \equiv c (\mod m)$ 。

由上面的定理可知，整数的集合被分成 $m$ 个不同的集合，这些集合称为“模 $m$ 剩余类（同余类）”，每个同余类中的任意两个整数都是模 $m$ 同余的。

例题：求模 $4$ 的 4 个同余类。 $\begin{aligned} \dots \equiv - 8 \equiv - 4 \equiv 0 \equiv 4 & \equiv 8 \equiv \dots (\mod 4) \\ \dots \equiv - 7 \equiv - 3 \equiv 1 \equiv 5 & \equiv 9 \equiv \dots (\mod 4) \\ \dots \equiv - 6 \equiv - 2 \equiv 2 \equiv 6 & \equiv 10 \equiv \dots (\mod 4) \\ \dots \equiv - 5 \equiv - 1 \equiv 3 \equiv 7 & \equiv 11 \equiv \dots (\mod 4) \end{aligned}$

这 4 个同余类可分别记为 $\overset{―}{0}, \overset{―}{1}, \overset{―}{2}, \overset{―}{3}$ ，如果要体现模数时，这 4 个同余类也可记为 ${\overset{―}{0}}_{4}, {\overset{―}{1}}_{4}, {\overset{―}{2}}_{4}, {\overset{―}{3}}_{4}$ 。

定理：若 $a, b, c$ 和 $m$ 是整数， $m > 0, a \equiv b (\mod m)$ ，则：

$a + c \equiv b + c (\mod m)$
$a - c \equiv b - c (\mod m)$
$a c \equiv b c (\mod m)$

上面定理表明，一个同余式两边同时加、减、乘上同一个整数，其同余关系不变。那么除法呢？也就是说一个同余式两边除以一个整数，同余关系还会保持吗？答案是不一定。我们看个例子：显然 $7 \cdot 2 \equiv 4 \cdot 2 (\mod 6)$ 是成立的，但我们不能在同余式两边同时消去因子 $2$ ，因为 $7 ≢ 4 (\mod 6)$ 。下面的定理给出了在同余式两边同时除以一个整数仍会保持的一个同余关系。

定理： 若 $a, b, c$ 和 $m$ 是整数， $m > 0, d = gcd (c, m)$ ，且有 $a c \equiv b c (\mod m)$ ，则： $a \equiv b (\mod m / d)$

例题：因为 $14 \equiv 8 (\mod 6)$ ，且 $gcd (2, 6) = 2$ ，所以有 $14 / 2 \equiv 8 / 2 (\mod 6 / 2)$ ，即 $7 \equiv 4 (\mod 3)$ 。

推论：若 $a, b, c$ 和 $m$ 是整数， $m > 0, gcd (c, m) = 1$ ，且有 $a c \equiv b c (\mod m)$ ，则： $a \equiv b (\mod m)$

定理：若 $a, b, c, d$ 和 $m$ 是整数， $m > 0, a \equiv b (\mod m)$ 且 $c \equiv d (\mod m)$ ，则：

$a + c \equiv b + d (\mod m)$
$a - c \equiv b - d (\mod m)$
$a c \equiv b d (\mod m)$

2.3. 线性同余方程

设 $x$ 是未知整数，形如 $a x \equiv b (\mod m)$ 的同余式称为“一元线性同余方程”。

首先注意到，若 $x = x_{0}$ 是同余方程 $a x \equiv b (\mod m)$ 的一个解，且 $x_{1} \equiv x_{0} (\mod m)$ ，则 $a x_{1} \equiv a x_{0} \equiv b (\mod m)$ ，所以 $x_{1}$ 也是一个解。因此，若一个模 $m$ 同余类的某个元素是解，则此同余类的所有元素都是解。于是，我们会问模 $m$ 的 $m$ 个同余类中有多少个给出方程的解：这相当于问方程有多少个模 $m$ 不同余的解。下面的定理告诉我们一元线性同余方程何时有解，在有解时方程有多少模 $m$ 不同余的解。

定理：设 $a, b$ 和 $m$ 是整数， $m > 0, gcd (a, m) = d$ 。若 $d ∤ b$ ，则 $a x \equiv b (\mod m)$ 无解。若 $d ∣ b$ ，则 $a x \equiv b (\mod m)$ 恰有 $d$ 个模 $m$ 不同余的解。

推论：若 $a$ 和 $m > 0$ 互素，且 $b$ 是整数，则线性同余方程 $a x \equiv b (\mod m)$ 有模 $m$ 的唯一解。

例题：找出 $9 x \equiv 12 (\mod 15)$ 的所有解。首先注意到 $gcd (9, 15) = 3$ 且 $3 ∣ 12$ ，所以这个同余方程恰有 $3$ 个不同余的解。它的解显然会满足线性丢番图方程 $9 x - 15 y = 12$ ，根据节 1.5 中介绍的定理，我们可以通过先找到一个特解，再加上 $15 / gcd (9, 15) = 5$ 的适当倍数来求得所有的解。容易验证 $x_{0} = 8, y_{0} = 4$ 是线性丢番图方程的一个特解，由节 1.5 中的定理可知， $x = 8 + (15 / gcd (9, 15)) k = 8 + 5 k$ 是线性丢番图方程的所有解（其中 $k$ 是整数）。由前面的定理知 $9 x \equiv 12 (\mod 15)$ 恰有 $3$ 个不同余的解，取恰当的 $k$ 可找到 $3$ 个模 $15$ 不同余解 $x = 3, x = 8, x = 13$ 。从而，这个同余方程的所有解为 $x = 3 + 15 n, x = 8 + 15 n, x = 13 + 15 n$ ，其中 $n$ 为整数。

2.4. 中国剩余定理

中国剩余定理：设 $m_{1}, m_{2}, \dots, m_{r}$ 是两两互素的正整数，则同余方程组 $\begin{aligned} x & \equiv a_{1} (\mod m_{1}) \\ x & \equiv a_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv a_{r} (\mod m_{r}) \end{aligned}$ 有模 $M = m_{1} m_{2} \dots m_{r}$ 的唯一解。记 $M_{i} = M / m_{i}$ ，设 $t_{i} = M_{i}^{- 1}$ 为 $M_{i}$ 的模 $m_{i}$ 的数论倒数，即满足 $t_{i} M_{i} \equiv 1 (\mod m_{i})$ ，则前面同余方程组的通解为 $x = k M + \sum_{i = 1}^{r} a_{i} t_{i} M_{i}$ ，其中 $k$ 是整数。在模 $M$ 的意义下，同余方程组只有一个解： $x = \sum_{i = 1}^{r} a_{i} t_{i} M_{i} (\mod M)$

例题：求解《孙子算经》有个“物不知数”问题：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

也就是说，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

这里的线性同余方程组为： $\begin{aligned} x & \equiv 2 (\mod 3) \\ x & \equiv 3 (\mod 5) \\ x & \equiv 2 (\mod 7) \end{aligned}$ 三个模数 $m_{1} = 3, m_{2} = 5, m_{3} = 7$ ，它们的乘积 $M = m_{1} m_{2} m_{3} = 105$ ，对应的 $M_{1} = M / 3 = 35, M_{2} = M / 5 = 21, M_{3} = M / 7 = 15$ ，可以计算出相应的数论倒数分别为 $t_{1} = 2, t_{2} = 1, t_{3} = 1$ ，所以同余方程组的通解为 $x = k M + \sum_{i = 1}^{r} a_{i} t_{i} M_{i} = 105 k + 2 \cdot 2 \cdot 35 + 3 \cdot 1 \cdot 21 + 2 \cdot 1 \cdot 15 = 105 k + 233$ 其中 $k$ 为整数。 $x$ 的最小正整数解 $x = 233 (\mod 105) = 23$ ，这时 $k = - 2$ 。

3. 特殊的同余式

3.1. Wilson's Theorem

威尔逊定理给出了判定一个自然数是否为素数充要条件。即 $n$ 是素数的充要条件是： $(n - 1)! + 1$ 是 $n$ 的倍数。

表 1 是 $n \leq 20$ 时， $(n - 1)! + 1 (\mod n)$ 的取值情况。从表中看，显然当 $n$ 是素数时， $(n - 1)! + 1 (\mod n)$ 确实为 $0$ ，也就是说当 $n$ 是素数时， $(n - 1)! + 1$ 确实是 $n$ 的倍数。

Table 1: $(n - 1)! + 1$ 是 $n$ 的倍数时（即第 3 列为 0 时）， $n$ 是素数
$n$	$(n - 1)!$	$(n - 1)! + 1 (\mod n)$
2	1	0
3	2	0
4	6	3
5	24	0
6	120	1
7	720	0
8	5040	1
9	40320	1
10	362880	1
11	3628800	0
12	39916800	1
13	479001600	0
14	6227020800	1
15	87178291200	1
16	1307674368000	1
17	20922789888000	0
18	355687428096000	1
19	6402373705728000	0
20	121645100408832000	1

一般把威尔逊定理描述为同余式的形式，即： 如果 $p$ 是素数，则 $(p - 1)! \equiv - 1 (\mod p)$ 。

威尔逊定理的逆也成立，即： $n$ 是正整数且 $n \geq 2$ ，如果 $(p - 1)! \equiv - 1 (\mod p)$ ，则 $p$ 是素数。

3.2. Fermat's Little Theorem

费马小定理：如果 $p$ 是素数， $a$ 是整数，并且 $p ∤ a$ （即 $p$ 不是 $a$ 的因子），则 $a^{p - 1} \equiv 1 (\mod p)$

比如， $a = 2, p = 7$ ，根据费马小定理有 $2^{7 - 1} \equiv 1 (\mod 7)$ 。

3.3. Euler's Theorem

欧拉定理：如果 $a$ 和 $n$ 是互素的正整数，则有 $a^{φ (n)} \equiv 1 (\mod n)$

我们知道，如果 $n$ 是素数，则有 $φ (n) = n - 1$ 。所以， 欧拉定理是费马小定理的更一般形式，它把费马小定理推广到了模不是素数的情形。

4. 乘性函数

定义（算术函数）：定义在所有正整数上的函数称为算术函数。

定义（乘性函数）：算术函数 $f$ 如果满足对任意两个互素的正整数 $n$ 和 $m$ ，均有 $f (m m) = f (m) f (n)$ ，就称为乘性函数（或积性函数），如果对任意两个正整数 $n$ 和 $m$ ，均有 $f (m n) = f (m) f (n)$ ，就称为完全乘性（或完全积性）函数。

例题：对所有 $n$ ，函数 $f (n) = 1$ 是一个完全乘性函数，所以也是乘性函数，因为 $f (m m) = 1$ ， $f (m) = 1$ 和 $f (n) = 1$ ，从而有 $f (m n) = f (m) f (n)$ ，类似地，函数 $g (n) = n$ 是一个完全乘性函数，也是乘性函数，因为 $g (m n) = m n = g (m) g (n)$ 。

定理：如果 $f$ 是一个乘性函数，对任意正整数 $n$ 有素数幂分解 $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{s}^{a_{s}}$ ，那么 $f (n) = f (p_{1}^{a_{1}}) f (p_{2}^{a_{2}}) \dots f (p_{s}^{a_{s}})$ 。

证明：我们将基于整数 $n$ 的素数幂分解中出现的不同素数的个数，用数学归纳法来证明这个定理。如果 $n$ 在它的素数幂分解中只有一个素数，即存在某个素数使得 $n = p_{1}^{a_{1}}$ ，那么定理显然成立。

假设定理对素数幂分解中出现 $k$ 个不同素数的所有整数成立，现在假设整数 $n$ 的素数幂分解中出现 $k + 1$ 个不同的素数，即 $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}} p_{k + 1}^{a_{k + 1}}$ 。因为 $f$ 是乘性函数且 $gcd (p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}, p_{k + 1}^{a_{k + 1}}) = 1$ ，可推出 $f (n) = f (p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}) f (p_{k + 1}^{a_{k + 1}})$ 。由归纳假设知 $f (p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}) = f (p_{1}^{a_{1}}) f (p_{2}^{a_{2}}) \dots f (p_{k}^{a_{k}})$ ；从而得 $f (n) = f (p_{1}^{a_{1}}) f (p_{2}^{a_{2}}) \dots f (p_{k}^{a_{k}}) f (p_{k + 1}^{a_{k + 1}})$ 。证毕。

4.1. 欧拉 $φ$ 函数

定义：在数论中，对正整数 $n$ ，欧拉函数 $φ (n)$ 是小于等于 $n$ 的正整数中与 $n$ 互素的数的数目。比如 $φ (8) = 4$ ，因为小于等于 $8$ 的正整数中，有 $1, 3, 5, 7$ 共 $4$ 个数与 $8$ 互素。

4.1.1. 欧拉 $φ$ 函数相关定理 I

定理：如果 $p$ 是素数，那么 $φ (p) = p - 1$ 。反之，如果 $p$ 是一个正整数且满足 $φ (p) = p - 1$ ，那么 $p$ 是素数。

证明：如果 $p$ 是素数，那么任意小于 $p$ 的正整数都是与 $p$ 互素的，因为有 $p - 1$ 个这样的整数，所以有 $φ (p) = p - 1$ 。反之，如果 $p$ 不是素数，那么 $p = 1$ 或者 $p$ 是合数。如果 $p = 1$ ，那么 $φ (p) \neq p - 1$ ，因为 $φ (1) = 1$ 。如果 $p$ 是合数，那么 $p$ 有一个因子 $d$ 满足 $1 < d < p$ ，显然 $p$ 和 $d$ 不互素，由于 $p - 1$ 个整数 $1, 2, \dots, p - 1$ 中至少有一个整数，即 $d$ 是不和 $p$ 互素的，那么 $φ (p) \leq p - 2$ 。因此，如果 $φ (p) = p - 1$ ，那么 $p$ 必是素数。

定理：设 $p$ 是素数， $a$ 是一个正整数，那么 $φ (p^{a}) = p^{a} - p^{a - 1}$ 。

证明：所有不超过 $p^{a}$ ，且和 $p$ 不互素的正整数就是那些不超过 $p^{a}$ ，且能够被 $p$ 整除的所有整数，即 $k p$ ，其中 $1 \leq k \leq p^{a - 1}$ 。因为恰有 $p^{a - 1}$ 个这样的整数，所以存在 $p^{a} - p^{a - 1}$ 个不超过 $p^{a}$ ，且和 $p^{a}$ 互素的正整数，所以 $φ (p^{a}) = p^{a} - p^{a - 1}$ 。

例题：计算 $φ (5^{3}), φ (2^{10})$ 。利用上面定理有， $φ (5^{3}) = 5^{3} - 5^{2} = 100$ ，类似地有 $φ (2^{10}) = 2^{10} - 2^{9} = 512$ 。

定理： 欧拉 $φ$ 函数是个乘性函数。也就是说，设 $m$ 和 $n$ 是互素的正整数，那么 $φ (m n) = φ (m) φ (n)$ 。

4.1.2. 欧拉 $φ$ 函数计算公式

设 $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ 为正整数 $n$ 的素数幂分解，那么欧拉 $φ$ 函数可以用下面公式计算： $φ (n) = n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{k}})$

例题：求 $φ (100)$ 。利用 $φ$ 函数计算公式，有： $φ (100) = φ (2^{2} 5^{2}) = 100 (1 - \frac{1}{2}) (1 - \frac{1}{5}) = 40$

例题：求 $φ (720)$ 。利用 $φ$ 函数计算公式，有： $φ (720) = φ (2^{4} 3^{2} 5) = 720 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 192$

4.1.3. 欧拉 $φ$ 函数相关定理 II

定理：设 $n$ 是一个大于 $2$ 的正整数，那么 $φ (n)$ 是偶数。

定理：设 $n$ 为一个正整数，那么 $\sum_{d ∣ n} φ (d) = n$ 。也就是说， $φ$ 函数在 $n$ 的所有正因子处的值之和为 $n$ 。

我们使用 $n = 18$ 来验证一下上面的定理。 $n = 18$ 的所有正因子有 $1, 2, 3, 6, 9, 18$ ，容易分别计算出 $φ (1) = 1, φ (2) = 1, φ (3) = 2, φ (6) = 2, φ (9) = 6, φ (18) = 6$ ， $\sum_{d ∣ n} φ (d) = φ (1) + φ (2) + φ (3) + φ (6) + φ (9) + φ (18) = 1 + 1 + 2 + 2 + 6 + 6 = 18 = n$ 。

4.2. 因子和函数、因子个数函数

定义：因子和函数 $σ$ 定义为整数 $n$ 的所有正因子之和，记为 $σ (n)$ 。比如 $σ (12) = 1 + 2 + 3 + 4 + 6 + 12 = 28$ 。

定义：因子个数函数 $τ$ 定义为正整数 $n$ 的所有正因子个数，记为 $τ (n)$ 。比如 $τ (12) = 6$ 。

因子和函数、因子个数函数都是乘性函数。

5. Primitive Roots

5.1. 整数的阶

由欧拉定理可知，如果 $a$ 和 $n$ 是互素的正整数，则有 $a^{φ (n)} \equiv 1 (\mod n)$ ，从而可得到结论：如果 $a$ 和 $n$ 是互素的正整数，至少有一个正整数 $x$ 会满足 $a^{x} \equiv 1 (\mod n)$ 。

定义：设 $a$ 和 $n$ 是互素的正整数， 我们把使得 $a^{x} \equiv 1 (\mod n)$ 成立的最小的正整数 $x$ 称为 $a$ 模 $n$ 的阶（Order of $a$ modulo $n$ ），记为 ${ord}_{n} a$ 。

例题：求解 $2$ 模 $7$ 的阶。我们计算 $2$ 的各次幂对模 $7$ 的运算： $\begin{array}{r} 2^{1} \equiv 2 (\mod 7) \\ 2^{2} \equiv 4 (\mod 7) \\ 2^{3} \equiv 1 (\mod 7) \end{array}$ 满足 $2^{x} \equiv 1 (\mod 7)$ 的最小正整数是 $3$ ，所以有 ${ord}_{7} 2 = 3$ 。

例题：求解 $3$ 模 $7$ 的阶。我们计算 $3$ 的各次幂对模 $7$ 的运算： $\begin{array}{r} 3^{1} \equiv 3 (\mod 7) \\ 3^{2} \equiv 2 (\mod 7) \\ 3^{3} \equiv 6 (\mod 7) \\ 3^{4} \equiv 4 (\mod 7) \\ 3^{5} \equiv 5 (\mod 7) \\ 3^{6} \equiv 1 (\mod 7) \end{array}$ 满足 $3^{x} \equiv 1 (\mod 7)$ 的最小正整数是 $6$ ，所以有 ${ord}_{7} 3 = 6$ 。

5.1.1. 整数的阶相关定理

同余式 $a^{x} \equiv 1 (\mod n)$ 的全部解是多少？下面定理给出了答案。

定理：如果 $a$ 和 $n$ 是互素的整数且 $n > 0$ ，那么正整数 $x$ 是同余式 $a^{x} \equiv 1 (\mod n)$ 的一个解当且仅当 ${ord}_{n} a ∣ x$ （也就是说 $x$ 是 ${ord}_{n} a$ 的倍数）。

证明：如果 ${ord}_{n} a ∣ x$ ，那么 $x = k \cdot {ord}_{n} a$ ，其中 $k$ 为正整数。因此有： $a^{x} = a^{k \cdot {ord}_{n} a} = (a^{{ord}_{n} a})^{k} = 1 (\mod n)$ 反过来，如果 $a^{x} \equiv 1 (\mod n)$ ，首先用带余除法记为： $x = q \cdot {ord}_{n} a + r$ 其中 $0 \leq r < {ord}_{n} a$ ，由上面等式有 $a^{x} = q^{q \cdot {ord}_{n} a + r} = (a^{{ord}_{n} a})^{q} a^{r} \equiv a^{r} (\mod n)$ 因为 $a^{x} = 1 (\mod n)$ ，所以 $a^{r} = 1 (\mod n)$ ，从不等式 $0 \leq r < {ord}_{n} a$ 得， $r = 0$ , 这是因为由定义知 $y = {ord}_{n} a$ 是使得 $a^{y} = 1 (\mod n)$ 成立的最小的正整数。由 $r = 0$ 知， $x = q \cdot {ord}_{n} a$ ，故有 ${ord}_{n} a ∣ x$ 。

例题：请问 $x = 10$ 和 $x = 15$ 是否是方程 $2^{x} \equiv 1 (\mod 7)$ 的解。由节 5.1 中的例子，我们知道 ${ord}_{7} 2 = 3$ ，因为 $10$ 不是 $3$ 的倍数，而 $15$ 是 $3$ 的倍数，所以根据上面的定理有 $10$ 不是 $2^{x} \equiv 1 (\mod 7)$ 的解，而 $15$ 是 $2^{x} \equiv 1 (\mod 7)$ 的解。

推论： 如果 $a$ 和 $n$ 是互素的整数，且 $n > 0$ ，那么 ${ord}_{n} a ∣ φ (n)$ 。 这是一个很有用的推论，通俗讲就是 $a$ 和 $n$ 是互素时， $a$ 模 $n$ 的阶（即 ${ord}_{n} a$ ）一定是 $φ (n)$ 的因子。

我们在计算整数的阶时，可以利用上面推论作为一种简便方法。下面的例子示范了相应的步骤。

例题：求解 $5$ 模 $17$ 的阶。首先注意到 $φ (17) = 16$ ，因为 $16$ 的因子只有 $1, 2, 4, 8, 16$ 由推论知它们是 ${ord}_{17} 5$ 所有可能的取值。又因为 $\begin{array}{r} 5^{1} \equiv 5 (\mod 17) \\ 5^{2} \equiv 8 (\mod 17) \\ 5^{4} \equiv 13 (\mod 17) \\ 5^{8} \equiv 16 (\mod 17) \\ 5^{16} \equiv 1 (\mod 17) \end{array}$ 所以 ${ord}_{17} 5 = 16$ 。

5.2. 原根定义

在节 5.1.1 中提到了：如果 $r$ 和 $n$ 是互素，则 $r$ 模 $n$ 的阶（即 ${ord}_{n} r$ ）一定是 $φ (n)$ 的因子。显然 $φ (n)$ 因子中最大的数就是 $φ (n)$ 本身，我们把 ${ord}_{n} r$ 恰好等于 $φ (n)$ 时的 $r$ 称为模 $n$ 的原根。

定义（原根）：如果 $r$ 和 $n$ 是互素的整数且 $n > 0$ ，那么当 ${ord}_{n} r = φ (n)$ 时，称 $r$ 是模 $n$ 的原根（Primitive Root）。

例题：前面已证明 ${ord}_{7} 3 = 6$ ，而 $φ (7) = 6$ ，因此， $3$ 是模 $7$ 的一个原根。相似的，由于 ${ord}_{7} 5 = 6$ ，所以 $5$ 也是模 $7$ 的一个原根。这个例子告诉我们模 $n$ 的原根可能不止一个。

表 2 展示了 $n$ 为较小值时，模 $n$ 的所有原根。

Table 2: 模 $n$ 的所有原根， $n \leq 31$
$n$	primitive roots modulo $n$	$φ (n)$
1	0	1
2	1	1
3	2	2
4	3	2
5	2, 3	4
6	5	2
7	3, 5	6
8		4
9	2, 5	6
10	3, 7	4
11	2, 6, 7, 8	10
12		4
13	2, 6, 7, 11	12
14	3, 5	6
15		8
16		8
17	3, 5, 6, 7, 10, 11, 12, 14	16
18	5, 11	6
19	2, 3, 10, 13, 14, 15	18
20		8
21		12
22	7, 13, 17, 19	10
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22
24		8
25	2, 3, 8, 12, 13, 17, 22, 23	20
26	7, 11, 15, 19	12
27	2, 5, 11, 14, 20, 23	18
28		12
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28
30		8
31	3, 11, 12, 13, 17, 21, 22, 24	30

从表中可以发现， $2$ 是很多数的最小原根。

5.3. 原根的存在性

并非所有整数都有原根。 比如模 $8$ 就没有原根。因为比 $8$ 小且与 $8$ 互素的正整数只有 $1, 3, 5, 7$ ，并且 ${ord}_{8} 1 = 1, {ord}_{8} 3 = {ord}_{8} 5 = {ord}_{8} 7 = 2$ ，因为 $φ (8) = 4$ ，所以没有模 $8$ 的原根。

在前 $30$ 个正整数中， $2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27$ 和 $29$ 都有原根；而 $8, 12, 15, 16, 20, 21, 24, 28$ 和 $30$ 没有原根。这里不一一验证。

定理：正整数 $n$ ， $n > 1$ 存在原根的充要条件是： $n = 2, 4, p^{t}, 2 p^{t}$ 其中 $p$ 是奇素数且 $t$ 是正整数。

如果模 $n$ 有原根，则它的原根个数为 $φ (φ (n))$ 。当 $p$ 为素数时，模 $p$ 的原根个数是 $φ (φ (p)) = φ (p - 1)$ 。

5.4. 原根性质

如果 $g, n$ 是互素的正整数（即 $gcd (g, n) = 1$ ），且 $g$ 是模 $n$ 的原根，那么原根 $g$ 是整数模 $n$ 乘法群 $(Z / n Z)^{⋆}$ 的生成元。

例如，当 $n = 7$ 时，整数模 $7$ 乘法群 $(Z / 7 Z)^{⋆}$ 的元素是 ${1, 2, 3, 4, 5, 6}$ 。表 2 中介绍了模 $7$ 的原根是 $3, 5$ ，从而 $3, 5$ 都是整数模 $7$ 乘法群 $(Z / 7 Z)^{⋆}$ 的生成元。 $3$ 是整数模 $7$ 乘法群 $(Z / 7 Z)^{⋆}$ 的生成元，其验证如下： $\begin{array}{r} 3^{1} \equiv 3 (\mod 7) \\ 3^{2} \equiv 2 (\mod 7) \\ 3^{3} \equiv 6 (\mod 7) \\ 3^{4} \equiv 4 (\mod 7) \\ 3^{5} \equiv 5 (\mod 7) \\ 3^{6} \equiv 1 (\mod 7) \end{array}$ $5$ 是整数模 $7$ 乘法群 $(Z / 7 Z)^{⋆}$ 的生成元，其验证如下： $\begin{array}{r} 5^{1} \equiv 5 (\mod 7) \\ 5^{2} \equiv 4 (\mod 7) \\ 5^{3} \equiv 6 (\mod 7) \\ 5^{4} \equiv 2 (\mod 7) \\ 5^{5} \equiv 3 (\mod 7) \\ 5^{6} \equiv 1 (\mod 7) \end{array}$

下面看一个合数的例子。当 $n = 9$ 时，整数模 $9$ 乘法群 $(Z / 9 Z)^{⋆}$ 的元素是 ${1, 2, 4, 5, 7, 8}$ 。表 2 中介绍了模 $9$ 的原根是 $2, 5$ ，从而 $2, 5$ 都是整数模 $9$ 乘法群 $(Z / 9 Z)^{⋆}$ 的生成元。 $2$ 是整数模 $9$ 乘法群 $(Z / 9 Z)^{⋆}$ 的生成元，其验证如下： $\begin{array}{r} 2^{1} \equiv 2 (\mod 9) \\ 2^{2} \equiv 4 (\mod 9) \\ 2^{3} \equiv 8 (\mod 9) \\ 2^{4} \equiv 7 (\mod 9) \\ 2^{5} \equiv 5 (\mod 9) \\ 2^{6} \equiv 1 (\mod 9) \end{array}$ $5$ 是整数模 $9$ 乘法群 $(Z / 9 Z)^{⋆}$ 的生成元，其验证如下： $\begin{array}{r} 5^{1} \equiv 5 (\mod 9) \\ 5^{2} \equiv 7 (\mod 9) \\ 5^{3} \equiv 8 (\mod 9) \\ 5^{4} \equiv 4 (\mod 9) \\ 5^{5} \equiv 2 (\mod 9) \\ 5^{6} \equiv 1 (\mod 9) \end{array}$

5.5. 指数算术（离散对数）

由上一节的结论可知。假设 $g$ 是模 $n$ 的一个原根，如果 $a$ 是一个与 $n$ 互素的整数，那么存在唯一的一个满足 $1 \leq x \leq φ (n)$ 的整数 $x$ ，使得： $g^{x} \equiv a (\mod n)$ 成立，这个唯一的 $x$ 称为“ $a$ 对模 $n$ 的以 $g$ 为底的指数”（或者称“离散对数”，后文会介绍为什么称为“离散对数”），记为 $x = {ind}_{g} a$ ，在这个记号中省略了模数 $n$ 。

例题：设 $n = 7$ ，前面介绍过 $3$ 是模 $7$ 的一个原根，有： $\begin{array}{r} 3^{1} \equiv 3 (\mod 7) \\ 3^{2} \equiv 2 (\mod 7) \\ 3^{3} \equiv 6 (\mod 7) \\ 3^{4} \equiv 4 (\mod 7) \\ 3^{5} \equiv 5 (\mod 7) \\ 3^{6} \equiv 1 (\mod 7) \end{array}$ 如果使用 ${ind}_{g} a$ 记号的话，对于模 $7$ 有： $\begin{array}{r} {ind}_{3} 3 = 1 \\ {ind}_{3} 2 = 2 \\ {ind}_{3} 6 = 3 \\ {ind}_{3} 4 = 4 \\ {ind}_{3} 5 = 5 \\ {ind}_{3} 1 = 6 \end{array}$

例题：设 $n = 7$ ，前面介绍过 $5$ 也是模 $7$ 的一个原根，有： $\begin{array}{r} 5^{1} \equiv 5 (\mod 7) \\ 5^{2} \equiv 4 (\mod 7) \\ 5^{3} \equiv 6 (\mod 7) \\ 5^{4} \equiv 2 (\mod 7) \\ 5^{5} \equiv 3 (\mod 7) \\ 5^{6} \equiv 1 (\mod 7) \end{array}$ 如果使用 ${ind}_{g} a$ 记号的话，对于模 $7$ 有： $\begin{array}{r} {ind}_{5} 5 = 1 \\ {ind}_{5} 4 = 2 \\ {ind}_{5} 6 = 3 \\ {ind}_{5} 2 = 4 \\ {ind}_{5} 3 = 5 \\ {ind}_{5} 1 = 6 \end{array}$

5.5.1. 和对数相似的性质

定理：假设 $g$ 是模 $n$ 的一个原根，并且 $a$ 和 $b$ 是均与 $n$ 互素的整数，那么有：

${ind}_{g} 1 \equiv 0 (\mod φ (n))$
${ind}_{g} (a b) \equiv {ind}_{g} a + {ind}_{g} b (\mod φ (n))$
${ind}_{g} (a^{k}) \equiv k \cdot {ind}_{g} a (\mod φ (n))$ ，其中 $k$ 是正整数。

从上面定理可知，模 $n$ 的指数算术拥有和对数相似的性质（只需将等式用模 $φ (n)$ 的同余式来代替），这就是称其为“离散对数”的原因。

下面通过例子来介绍一下这个定理。设 $n = 7$ 有 $φ (7) = 6$ ，前面介绍过 $g = 5$ 是模 $7$ 的一个原根，上一节介绍了有： $\begin{array}{r} {ind}_{5} 5 = 1 \\ {ind}_{5} 4 = 2 \\ {ind}_{5} 6 = 3 \\ {ind}_{5} 2 = 4 \\ {ind}_{5} 3 = 5 \\ {ind}_{5} 1 = 6 \end{array}$ 下面用特例来验证上前面的定理：

对于定理第 1 条， ${ind}_{5} 1 \equiv 0 (\mod φ (7))$ 显然是成立的，因为 $6 \equiv 0 (\mod 6)$ 成立。
对于定理第 2 条，假设 $a = 2, b = 3$ ，式子 ${ind}_{5} (2 \cdot 3) \equiv {ind}_{5} 2 + {ind}_{5} 3 (\mod 6)$ 也显然成立，因为左边 ${ind}_{5} (2 \cdot 3) = {ind}_{5} 6 = 3$ ，而右边 ${ind}_{5} 2 + {ind}_{5} 3 = 4 + 5 = 9 \equiv 3 (\mod 6)$ 。
对于定理第 3 条，假设 $a = 3, k = 4$ ，式子 ${ind}_{5} (3^{4}) \equiv 4 \cdot {ind}_{5} 3 (\mod 6)$ 也会成立。因为左边 ${ind}_{5} (3^{4}) = {ind}_{5} 81 = {ind}_{5} 4 = 2$ （式子中从 $81$ 到 $4$ 是一个模 $7$ 的运算），而右边 $4 \cdot {ind}_{5} 3 = 4 \cdot 5 = 20 \equiv 2 (\mod 6)$ 。

5.5.2. 寻找离散对数的困难

给定一个素数 $p$ 和它的一个原根 $g$ ，寻找整数 $a$ 对模 $p$ 的以 $g$ 为底的指数（离散对数）问题称为离散对数问题。这个问题被认为和分解整数有一样的计算难度，即求 $g^{x} \equiv a (\mod p)$ 中的 $x$ 比较困难。基于这个原因，它被用来作为很多公钥密码系统的基础，例如 ElGamal 密码系统和 Diffie-Hellman 公钥密码协议。

5.6. 原根的应用：ElGamal 密码系统

ElGamal 密码系统是 Taher Elgamal 在 1985 年发明的。其安全性依赖于求模大素数的离散对数的困难性。

下面以 Bob 通过 ElGamal 密码系统给 Alice 发送消息为例，介绍一下 ElGamal 密码系统。

Key Generation 过程如下：

Alice 选取一个大素数 $p$ ，找到模 $p$ 的一个原根 $g$ ；
Alice 在 ${2, \dots, p - 1}$ 中随机选择一个数 $x$ ，它就是私钥，只有 Alice 知道；
Alice 计算出 $h = g^{x} (\mod p)$ ；公钥就是三元组 $(p, g, h)$ ，公钥发送给 Bob。

Bob 加密消息 $m$ （要求 $2 \leq m \leq p - 1$ ）的过程：

Bob 在 ${2, \dots, p - 2}$ 中随机选择一个 $k$ ，计算 $c_{1} = g^{k} (\mod p)$ ；
Bob 计算 $c_{2} = m \cdot h^{k} (\mod p)$ ；
Bob 发送密文二元组 $(c_{1}, c_{2})$ 给 Alice。

Alice 解密密文 $(c_{1}, c_{2})$ 的过程：

Alice 使用公式 $m = c_{1}^{p - 1 - x} \cdot c_{2} (\mod p)$ 计算 $(c_{1}, c_{2})$ 对应的明文。

下面推导一下为什么使用 $c_{1}^{p - 1 - x} \cdot c_{2} (\mod p)$ 计算出来的值就是加密前的明文。 $\begin{aligned} c_{1}^{p - 1 - x} \cdot c_{2} & = (g^{k})^{p - 1 - x} \cdot m \cdot h^{k} (\mod p) \\ = (g^{p - 1})^{k} g^{- k x} \cdot m \cdot g^{x k} (\mod p) \\ = (g^{p - 1})^{k} \cdot m (\mod p) \\ = (1)^{k} \cdot m (\mod p) \\ = m (\mod p) \end{aligned}$ 上面推导中利用了欧拉定理：如果 $g$ 和 $n$ 是互素的正整数，则 $g^{φ (n)} \equiv 1 (\mod n)$ 。还利用了欧拉 $φ (n)$ 函数的性质：对于素数 $p$ 有 $φ (p) = p - 1$ 。

5.6.1. ElGamal 实例

表 3 中通过实例介绍了 ElGamal 密码系统 Key Generation/加密/解密的详细步骤。

Table 3: ElGamal 实例
Alice	on public network	Bob
选择素数 $p = 2539$ （为了演示方便使用了小素数）
寻找模 $p$ 的一个原根，这里取它的原根 $g = 2$
在 ${2, \dots, p - 1}$ 随机选择 $x = 14$ 为私钥
计算 $h = g^{x} = 2^{14} \equiv 1150 (\mod p)$
发送公钥 $(p, g, h)$ 给 Bob	$(p, g, h) = (2539, 2, 1150)$ -->	收到公钥
		设待加密的明文 $m = 1520$
		在 ${2, \dots, p - 2}$ 中随机选择一个 $k = 1443$
		计算 $\begin{aligned} c_{1} & = g^{k} (\mod p) \\ = 2^{1443} (\mod 2539) \\ \equiv 2141 (\mod 2539) \end{aligned}$
		计算 $\begin{aligned} c_{2} & = m \cdot h^{k} (\mod p) \\ = 1520 \cdot 1150^{1443} (\mod 2539) \\ \equiv 216 (\mod 2539) \end{aligned}$
收到密文	<-- $(c_{1}, c_{2}) = (2141, 216)$	发送密文 $(c_{1}, c_{2})$ 给 Alice
计算明文 $\begin{aligned} m & = c_{1}^{p - 1 - x} \cdot c_{2} \\ = 2141^{2539 - 1 - 14} \cdot 216 (\mod 2539) \\ = 1520 (\mod 2539) \end{aligned}$

6. Quadratic Residues

二次剩余（Quadratic Residues）是数论中的一个重要概念。

6.1. 二次剩余定义

定义：设 $n$ 是正整数， $a$ 是整数且满足 $gcd (a, n) = 1$ ，如果存在 $x \in Z_{n}^{*}$ 满足： $x^{2} \equiv a (\mod n)$ 则， $a$ 叫做“模 $n$ 的二次剩余”； 否则（即不存在 $x \in Z_{n}^{*}$ 满足上面要求）， $a$ 就叫做“模 $n$ 的二次非剩余”。一般用 ${QR}_{n}$ 表示模 $n$ 的二次剩余集合，用 ${QNR}_{n}$ 表示模 $n$ 的二次非剩余集合。

例题：求解哪些数是模 $11$ 的二次剩余。我们依次计算 $Z_{11}^{*}$ 中所有数（即 $1, 2, \dots, 10$ ）的平方，有 $\begin{aligned} 1^{2} & \equiv 1 (\mod 11) \\ 2^{2} & \equiv 4 (\mod 11) \\ 3^{2} & \equiv 9 (\mod 11) \\ 4^{2} & \equiv 5 (\mod 11) \\ 5^{2} & \equiv 3 (\mod 11) \\ 6^{2} & \equiv 3 (\mod 11) \\ 7^{2} & \equiv 5 (\mod 11) \\ 8^{2} & \equiv 9 (\mod 11) \\ 9^{2} & \equiv 4 (\mod 11) \\ 10^{2} & \equiv 1 (\mod 11) \end{aligned}$
所以， $1, 3, 4, 5, 9$ 是模 $11$ 的二次剩余，而 $2, 6, 7, 8, 10$ 就是模 $11$ 的二次非剩余。用集合记号表示就是 ${QR}_{11} = {1, 3, 4, 5, 9}$ ， ${QNR}_{11} = {2, 6, 7, 8, 10}$ 。

6.2. 二次剩余相关定理

定理：如果 $p$ 是奇素数，则在集合 $Z_{p}^{*} = {1, 2, \dots, p - 1}$ 所有元素中，模 $p$ 的二次剩余恰有 $(p - 1) / 2$ 个，二次非剩余恰有 $(p - 1) / 2$ 个。也就是说 $Z_{p}^{*}$ 被分成大小相等的两个子集 ${QR}_{p}$ 和 ${QNR}_{p}$ 。

上一节例子中介绍了 $p$ 取素数 $11$ 的情况，即 $Z_{11}^{*}$ 确实被分成大小相等的两个子集 ${QR}_{11} = {1, 3, 4, 5, 9}$ 和 ${QNR}_{11} = {2, 6, 7, 8, 10}$ 。

定理：设 $р$ 是素数， $r$ 是 $p$ 的原根， $a$ 是不被 $р$ 整除的整数，若 ${ind}_{r} a$ 是偶数，则 $a$ 是 $p$ 的二次剩余，若 ${ind}_{r} a$ 是奇数，则 $a$ 是 $p$ 的二次非剩余。

前面介绍过， $5$ 是模 $7$ 的原根，有： $\begin{array}{r} {ind}_{5} 5 = 1 \\ {ind}_{5} 4 = 2 \\ {ind}_{5} 6 = 3 \\ {ind}_{5} 2 = 4 \\ {ind}_{5} 3 = 5 \\ {ind}_{5} 1 = 6 \end{array}$ 根据上面定理有： $\begin{aligned} {ind}_{5} 5 & = 1 \\ {ind}_{5} 4 & = 2 \to 因为 2 是偶数，所以 4 是 7 的二次剩余 \\ {ind}_{5} 6 & = 3 \\ {ind}_{5} 2 & = 4 \to 因为 4 是偶数，所以 2 是 7 的二次剩余 \\ {ind}_{5} 3 & = 5 \\ {ind}_{5} 1 & = 6 \to 因为 6 是偶数，所以 1 是 7 的二次剩余 \end{aligned}$

6.3. Legendre Symbol

设 $p$ 是奇素数，勒让德符号（Legendre Symbol）定义为： $(\frac{a}{p}) = {\begin{cases} 1 & 若 a 是 p 的二次剩余, \\ - 1 & 若 a 是 p 的二次非剩余, \\ 0 & 若 a \equiv 0 (\mod p) . \end{cases}$

例题：给出 $(\frac{a}{11})$ 在 $a = 1, 2, \dots, 10, 11$ 的值。因为在节 6.1 中介绍过， $1, 3, 4, 5, 9$ 是模 $11$ 的二次剩余，而 $2, 6, 7, 8, 10$ 就是模 $11$ 的二次非剩余。从而： $\begin{aligned} (\frac{1}{11}) & = (\frac{3}{11}) = (\frac{4}{11}) = (\frac{5}{11}) = (\frac{9}{11}) = 1 \\ (\frac{2}{11}) & = (\frac{6}{11}) = (\frac{7}{11}) = (\frac{8}{11}) = (\frac{10}{11}) = - 1 \\ (\frac{11}{11}) & = 0 \end{aligned}$

6.4. 二次剩余的判定（欧拉判别法）

我们现在给出判定一个整数是否为某个素数的二次剩余的准则。这个准则在证明勒让德符号的性质时很有用。

欧拉判别法：设 $p$ 是奇素数，则： $(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (\mod p)$

例题：问 $5$ 是 $23$ 的二次剩余，还是二次非剩余？由于 $23$ 是奇素数，我们可以采用欧拉判别法。因为 $5^{(23 - 1) / 2} (\mod 23) \equiv 22 (\mod 23) \equiv - 1 (\mod 23)$ ，所以 $5$ 是否是 $23$ 的二次非剩余。

6.4.1. 二次剩余判定问题（QRP）

前面介绍了，当 $n$ 是奇素数时，使用欧拉判别法容易判定 $x \in Z_{n}^{*}$ 是否是 $n$ 的二次剩余。

但是，如果 $n$ 是一个合数，而且不知道它的分解，那么目前没有有效的方法来判定 $x \in Z_{n}^{*}$ 是否是 $n$ 的二次剩余。这被称为二次剩余判定问题（Quadratic Residuosity Problem），它是一个计算困难问题。

公钥密码体制 Goldwasser–Micali Cryptosystem 的安全性基于二次剩余判定问题。

6.5. Jacobi Symbol（Legendre Symbol 的推广）

设 $n$ 是正奇数，其素幂分解式为 $n = p_{1}^{t_{1}} p_{2}^{t_{2}} \dots p_{m}^{t_{m}}$ ，则雅可比符号（Jacobi Symbol）定义为： $(\frac{a}{n}) = {(\frac{a}{p_{1}})}^{t_{1}} {(\frac{a}{p_{2}})}^{t_{2}} \dots {(\frac{a}{p_{m}})}^{t_{m}}$ 其中等式右边的符号是勒让德符号。

如果 $n$ 是奇素数，显然雅可比符号和勒让德符号一致。

注：勒让德符号仅当 $n$ 为奇素数时才有定义，而雅可比符号的定义放宽了这个限制，把 $n$ 的范围扩展到了正奇数。所以，雅可比符号是勒让德符号的一种推广。

例题：求 $(\frac{2}{45})$ 和 $(\frac{109}{385})$ 。由雅可比符号的定义有： $(\frac{2}{45}) = (\frac{2}{3^{2} 5}) = {(\frac{2}{3})}^{2} (\frac{2}{5}) = (- 1)^{2} (- 1) = - 1$ 和 $\begin{aligned} (\frac{109}{385}) & = (\frac{109}{5 \cdot 7 \cdot 11}) \\ = (\frac{109}{5}) (\frac{109}{7}) (\frac{109}{11}) \\ = (\frac{4}{5}) (\frac{4}{7}) (\frac{10}{11}) \\ = {(\frac{2}{5})}^{2} {(\frac{2}{7})}^{2} (\frac{- 1}{11}) \\ = (- 1)^{2} 1^{2} (- 1) \\ = - 1 \end{aligned}$

6.5.1. 雅可比符号的性质

定理：设 $n$ 是正奇数， $a$ 和 $b$ 是与 $n$ 互素的正整数，则：

若 $a \equiv b (\mod n)$ ，则 $(\frac{a}{n}) = (\frac{b}{n})$
$(\frac{a b}{n}) = (\frac{a}{n}) (\frac{b}{n})$
$(\frac{- 1}{n}) = (- 1)^{(n - 1) / 2}$
$(\frac{2}{n}) = (- 1)^{(n^{2} - 1) / 8}$

雅可比符号的互反律：设 $n$ 和 $m$ 是互素的正奇数，则： $(\frac{n}{m}) (\frac{m}{n}) = (- 1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}}$

7. Modular Square Roots

本节介绍如何计算模一个整数的平方根。即已知 $a$ 和 $n$ ，求满足条件 $x^{2} \equiv a (\mod n)$ 的非负数 $x$ 。对应的解 $x$ 可记为 $x \overset{def}{=} \sqrt{a} (\mod n)$ 。显然，当 $a \in {QR}_{n}$ 时， $x$ 有解，当 $a \in {QNR}_{n}$ 时， $x$ 无解。

例：求 $3 (\mod 11)$ 的一个平方根。因为 $5^{2} \equiv 3 (\mod 11)$ ，所以 $5$ 满足要求；又因为 $6^{2} \equiv 3 (\mod 11)$ ，所以 $6$ 也满足要求。

例：求 $7 (\mod 11)$ 的一个平方根。 $7 \in {QNR}_{11}$ ，没有 $x$ 会满足 $x^{2} \equiv 7 (\mod 11)$ 。

7.1. 求模为素数时的平方根

7.1.1. 模为特殊情况 $p \equiv 3, 7 (\mod 8)$

当模数 $p$ 为素数，且满足 $p \equiv 3, 7 (\mod 8)$ 时。对于 $a \in {QR}_{p}$ ，则 $x = a^{(p + 1) / 4} (\mod p)$ 一定是 $a$ 模 $p$ 的平方根。

例：求 $5 (\mod 11)$ 的一个平方根。因为模数 $11$ 是素数，且 $11 \equiv 3 (\mod 8)$ ，所以我们可以直接使用上面结论，即 $x = 5^{(11 + 1) / 4} (\mod 11) = 4$ 是 $5 (\mod 11)$ 的一个平方根。容易验证这是对的，因为 $4^{2} \equiv 5 (\mod 11)$ 显然成立。

7.1.2. 模为特殊情况 $p \equiv 3 (\mod 4)$

当模数 $p$ 为素数，且满足 $p \equiv 3 (\mod 4)$ 时。对于 $a \in {QR}_{p}$ ，则 $x = a^{(p + 1) / 4} (\mod p)$ 一定是 $a$ 模 $p$ 的平方根。

7.1.3. 求模为一般素数时的平方根

如果模 $p$ 为一般素数， $a \in {QR}_{p}$ ，则可以使用 Tonelli–Shanks 算法求解 $a (\mod p)$ 的平方根。

7.2. 求模为合数时的平方根

7.2.1. 已知合数分解

如果模 $n$ 为合数，且已知合数的分解，那么使用图 1 所示算法可以求得模 $n$ 的平方根。

Figure 1: 模 $n$ 为合数，且已知合数的分解，求模 $n$ 的平方根

7.2.2. 未知合数分解

如果我们不知道模 $n$ 的分解，则没有有效算法可以求得模 $n$ 的平方根。在计算上，分解 $n$ 和求模 $n$ 的平方根是等价的。

8. 参考

本文主要摘自书籍：《初等数论及其应用（Elementary Number Theory and Its Applications）》和《现代密码学理论与实践（Modern Cryptography Theory and Practice）》