Elementary Number Theory

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

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

定理（算术基本定理）：每个大于 \(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）。

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

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

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

定理（欧几里得算法）：整数 \(a \ge b \gt 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\) 。

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

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

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

定理：设 \(a, b\) 是整数且 \(d=\gcd(a, b)\) 。如果 \(d \nmid c\) ，那么方程 \(ax+by=c\) 没有整数解。如果 \(d \mid c\) ，那么存在无穷多个整数解。另外，如果 \(x=x_0, y=y_0\) 是方程的一个特解，那么所有的解可以表示为 \[x=x_0+(b/d)n,y=y_0-(a/d)n\] 其中 \(n\) 是整数。

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

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

定义： 若 \(a\) 和 \(b\) 是整数，且 \(m \mid (a-b)\) ，则称 \(a\) 和 \(b\) 模 \(m\) 同余。 若 \(a\) 和 \(b\) 模 \(m\) 同余，则记 \(a \equiv b \pmod m\) 。若 \(m \nmid (a-b)\) ，则记 \(a \not\equiv b \pmod m\) ，并称 \(a\) 模 \(m\) 不同余于 \(b\) 。

例题：因为 \(9 \mid (22-4)\) ，所以 \(22=4 \pmod 9\) 。另外，因为 \(9 \nmid (13-5)\) ，所以 \(13 \not\equiv 5 \pmod 9\) 。

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

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

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

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

这 4 个同余类可分别记为 \(\overline{0},\overline{1},\overline{2},\overline{3}\) ，如果要体现模数时，这 4 个同余类也可记为 \(\overline{0}_4,\overline{1}_4,\overline{2}_4,\overline{3}_4\) 。

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

1. \(a+c \equiv b+c \pmod m\)
   
2. \(a-c \equiv b-c \pmod m\)
   
3. \(ac \equiv bc \pmod m\)
   

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

定理： 若 \(a,b,c\) 和 \(m\) 是整数， \(m \gt 0, d = \gcd(c,m)\) ，且有 \(ac \equiv bc \pmod m\) ，则： \(a \equiv b \pmod {m/d}\)

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

推论：若 \(a,b,c\) 和 \(m\) 是整数， \(m \gt 0, \gcd(c,m)=1\) ，且有 \(ac \equiv bc \pmod m\) ，则： \(a \equiv b \pmod m\)

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

1. \(a+c \equiv b+d \pmod m\)
   
2. \(a-c \equiv b-d \pmod m\)
   
3. \(ac \equiv bd \pmod m\)
   

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

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

定理：设 \(a, b\) 和 \(m\) 是整数， \(m \gt 0, \gcd(a, m) =d\) 。若 \(d \nmid b\) ，则 \(ax \equiv b \pmod m\) 无解。若 \(d \mid b\) ，则 \(ax \equiv b \pmod m\) 恰有 \(d\) 个模 \(m\) 不同余的解。

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

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

中国剩余定理：设 \(m_1,m_2,\cdots, m_r\) 是两两互素的正整数，则同余方程组 \[\begin{aligned} x & \equiv a_1 \pmod {m_1} \\ x & \equiv a_2 \pmod {m_2} \\ & \vdots \\ x & \equiv a_r \pmod {m_r} \end{aligned}\] 有模 \(M=m_1m_2 \cdots m_r\) 的唯一解。记 \(M_i = M/m_i\) ，设 \(t_i = M_i^{-1}\) 为 \(M_i\) 的模 \(m_i\) 的数论倒数，即满足 \(t_i M_i \equiv 1 \pmod {m_i}\) ，则前面同余方程组的通解为 \(x = kM + \sum_{i=1}^{r} a_i t_i M_i\) ，其中 \(k\) 是整数。在模 \(M\) 的意义下，同余方程组只有一个解： \[x = \sum_{i=1}^{r} a_i t_i M_i \pmod M\]

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

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

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

这里的线性同余方程组为： \[\begin{aligned} x & \equiv 2 \pmod {3} \\ x & \equiv 3 \pmod {5} \\ x & \equiv 2 \pmod {7} \end{aligned}\] 三个模数 \(m_1=3,m_2=5,m_3=7\) ，它们的乘积 \(M=m_1m_2m_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 = kM + \sum_{i=1}^{r} a_i t_i M_i = 105k + 2 \cdot 2 \cdot 35 + 3 \cdot 1 \cdot 21 + 2 \cdot 1 \cdot 15 = 105k+233\) 其中 \(k\) 为整数。 \(x\) 的最小正整数解 \(x= 233 \pmod {105} = 23\) ，这时 \(k=-2\) 。

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

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

Table 1: \((n-1)! + 1\) 是 \(n\) 的倍数时（即第 3 列为 0 时）， \(n\) 是素数

\(n\)	\((n-1)!\)	\((n-1)! + 1 \pmod 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 \pmod p\) 。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Table 2: 模 \(n\) 的所有原根， \(n \le 31\)

\(n\)	primitive roots modulo \(n\)	\(\varphi(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\) 是很多数的最小原根。

并非所有整数都有原根。 比如模 \(8\) 就没有原根。因为比 \(8\) 小且与 \(8\) 互素的正整数只有 \(1,3,5,7\) ，并且 \(\text{ord}_8 1 = 1, \text{ord}_8 3 = \text{ord}_8 5 = \text{ord}_8 7 = 2\) ，因为 \(\varphi(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 \gt 1\) 存在原根的充要条件是： \[n = 2,4,p^t,2p^t\] 其中 \(p\) 是奇素数且 \(t\) 是正整数。

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

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

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

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

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

例题：设 \(n=7\) ，前面介绍过 \(3\) 是模 \(7\) 的一个原根，有： \[\begin{aligned} 3^1 \equiv 3 \pmod 7 \\ 3^2 \equiv 2 \pmod 7 \\ 3^3 \equiv 6 \pmod 7 \\ 3^4 \equiv 4 \pmod 7 \\ 3^5 \equiv 5 \pmod 7 \\ 3^6 \equiv 1 \pmod 7 \end{aligned}\] 如果使用 \(\text{ind}_g a\) 记号的话，对于模 \(7\) 有： \[\begin{aligned} \text{ind}_3 3 = 1 \\ \text{ind}_3 2 = 2 \\ \text{ind}_3 6 = 3 \\ \text{ind}_3 4 = 4 \\ \text{ind}_3 5 = 5 \\ \text{ind}_3 1 = 6 \end{aligned}\]

例题：设 \(n=7\) ，前面介绍过 \(5\) 也是模 \(7\) 的一个原根，有： \[\begin{aligned} 5^1 \equiv 5 \pmod 7 \\ 5^2 \equiv 4 \pmod 7 \\ 5^3 \equiv 6 \pmod 7 \\ 5^4 \equiv 2 \pmod 7 \\ 5^5 \equiv 3 \pmod 7 \\ 5^6 \equiv 1 \pmod 7 \end{aligned}\] 如果使用 \(\text{ind}_g a\) 记号的话，对于模 \(7\) 有： \[\begin{aligned} \text{ind}_5 5 = 1 \\ \text{ind}_5 4 = 2 \\ \text{ind}_5 6 = 3 \\ \text{ind}_5 2 = 4 \\ \text{ind}_5 3 = 5 \\ \text{ind}_5 1 = 6 \end{aligned}\]

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

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

Key Generation 过程如下：

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

Bob 加密消息 \(m\) （要求 \(2 \le m \le p-1\) ）的过程：

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

Alice 解密密文 \((c_1,c_2)\) 的过程：

1. Alice 使用公式 \(m = c_1^{p-1-x} \cdot c_2 \pmod p\) 计算 \((c_1,c_2)\) 对应的明文。
   

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

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

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

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

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

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

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

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

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

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

欧拉判别法：设 \(p\) 是奇素数，则： \[\left({\frac {a}{p}}\right) \equiv a^{\frac{p-1}{2}} \pmod p\]

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

设 \(n\) 是正奇数，其素幂分解式为 \(n=p_1^{t_1}p_2^{t_2}\cdots p_m^{t_m}\) ，则雅可比符号（Jacobi Symbol）定义为： \[\left({\frac {a}{n}}\right)=\left({\frac {a}{p_1}}\right)^{t_1}\left({\frac {a}{p_2}}\right)^{t_2} \cdots \left({\frac {a}{p_m}}\right)^{t_m}\] 其中等式右边的符号是勒让德符号。

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

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

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