附录12 - 模 n 的原根

引理：给定 $a$ 和 $n$，$a^d \equiv 1 \pmod n$ 有正整数解，当且仅当 $\gcd(a, n) = 1$

证明必要性：
$\text{存在 } d \gt 0 \text{ 使得 } a^d \equiv 1 \pmod n \implies \gcd(a, n) = 1$
反证法，假设 $\gcd(a, n) > 1$，设 $p \gt 0$ 是 $a$ 和 $n$ 的一个公约数
因为 $a^d \equiv 1 \pmod n$，存在整数 $k$ 使得 $a^d = nk + 1$
$a^d - nk = 1$
因为 $p \mid a$ 于是 $p \mid a^d$，又有 $p \mid n$ 于是 $p \mid nk$。所以 $p \mid a^d - nk$
于是 $p \mid 1$。但一个大于 $0$ 的数 $p$ 是不可能整除 $1$ 的，这就推出了矛盾。
因此必有 $\gcd(a, n) = 1$。

证明充分性：
$\gcd(a, n) = 1 \implies \text{存在 } d \gt 0 \text{ 使得 } a^d \equiv 1 \pmod n$
考虑下面 $n + 1$ 个 $a$ 的正整数次方：
$a^1, a^2, a^3, a^4, \dots, a^{n+1}$
我们将这些数全部对 $n$ 取模（即求除以 $n$ 的余数）。
运用抽屉原理，一个数除以 $n$ 的余数，只能是 $0, 1, 2, \dots, n-1$ 这 $n$ 个数字中的某一个。把上面 $n+1$ 个余数分配给这 $n$ 个数，必然至少有两项余数相同。假设这两项分别是 $a^i$ 和 $a^j$，并且我们规定 $1 \le i \lt j$。
于是，我们可以写出同余式：
$a^i \equiv a^j \pmod n$
也就是：
$n \mid (a^j - a^i)$
提取公因式 $a^i$，得到：
$n \mid a^i \cdot (a^{j-i} - 1)$
已知 $a$ 与 $n$ 互素，那么 $a^i$ 也与 $n$ 互素。根据欧几里得引理：如果一个整数 $n$ 整除两个数的乘积 $X \cdot Y$，且 $n$ 与 $X$ 互素，那么 $n$ 必然整除 $Y$。于是必然有：
$n \mid (a^{j-i} - 1)$
转换回同余式的写法就是：
$a^{j-i} \equiv 1 \pmod n$
令 $d = j - i$，于是就得到了：
$a^d \equiv 1 \pmod n$

『模 $n$ 的阶』：设 $a$ 与 $n$ 互素（即 $\gcd(a, n) = 1$）。
使得同余式 $a^d \equiv 1 \pmod n$ 成立的最小正整数 $d$，称为 $a$ 模 $n$ 的阶，记作 $\text{ord}_n(a)$。

设 $a$ 在模 $n$ 下的阶是 $d$。令 $\langle a \rangle = \left\{1, a, a^2, \cdots, a^{d-1}\right\}$，$\langle a \rangle$ 称为由 $a$ 生成的循环子群（Cyclic Subgroup generated by $a$），有下列性质：

1. $1, a, a^2, \cdots, a^{d-1}$ 这 $d$ 个数在模 $n$ 下彼此不同，并且都与 $n$ 互素。
2. $\langle a \rangle$ 对模 $n$ 乘法封闭：里面任意两个数相乘仍在 $\langle a \rangle$ 中。
3. $\langle a \rangle$ 中每个元素都存在乘法逆元
4. 将 $\langle a \rangle$ 中每个元素都乘以 $a^i (i \ge 0)$，得到的集合仍然是 $\langle a \rangle$
5. 如果整数 $k$ 使得 $a^k \equiv 1 \pmod n$，那么必有 $d \mid k$（阶的整除性质）

证明性质 1 ($\langle a \rangle$ 中数都与 $n$ 互素)：

因为 $a$ 与 $n$ 互素，$a^k$ 必定也与 $n$ 互素，设 $a^k$ 除以 $n$ 的余数是 $r$，我们要证明 $r$ 也与 $n$ 互素。假设 $r$ 与 $n$ 不互素，即它们有一个大于 $1$ 的公约数 $p$，由于 $p \mid r$ 且 $p \mid nq$，必有 $p \mid (nq + r)$，即 $p \mid a^k$，于是 $a^k$ 和 $n$ 存在 $p$ 这个公约数，与 $a^k$ 必定也与 $n$ 互素

证明性质 1 ($1, a, a^2, \cdots, a^{d-1}$ 彼此不同)：

假设集合 $\langle a \rangle$ 中存在两个相同的元素。也就是说，存在 $0 \le j < i \le d-1$，使得：
$a^i \equiv a^j \pmod n$
根据同余的定义，这等价于：
$n \mid (a^i - a^j) \implies n \mid a^j(a^{i-j} - 1)$
由于 $\gcd(a^j, n) = 1$，根据欧几里得引理，$n$ 必须整除后面那一项：
$n \mid (a^{i-j} - 1) \implies a^{i-j} \equiv 1 \pmod n$
此时，我们来看指数 $i-j$。因为 $0 \le j < i \le d-1$，所以 $i-j$ 是一个正整数，且满足：
$0 < i - j \le d - 1 < d$
我们竟然找到了一个比 $d$ 更小的正整数 $i-j$，使得 $a$ 的该次幂模 $n$ 等于 $1$。但这直接违背了“$d$ 是满足该条件的最小正整数（即阶）”的定义。矛盾产生！因此，假设不成立，这 $d$ 个数在模 $n$ 下必然两两不同。

证明性质 2、3:

任意整数 $k$，用 $d$ 作带余除法：$k = d n + r (0 \le r \le d - 1)$，于是
$a^k = a^{d n + r} = {(a^d)}^n\cdot a^r \equiv 1^n\cdot a^r \equiv a^r \pmod p$
这就证明了 $a$ 的任意整数次方都在 $\langle a \rangle$ 中，即 $\langle a \rangle$ 对模乘法封闭，即性质2。
因为 $a^k \equiv a^r$，${(a^k)}^{-1} \equiv {(a^r)}^{-1}$，而 $a^r \cdot a^{d - r} \equiv a^d \equiv 1$，所以 $a^{d-r}$ 就是 $a^k$ 的乘法逆元，性质3得证。

证明性质 4:

将 $\langle a \rangle$ 中每个元素都乘以 $a^k (k \ge 0)$，变为了：
$\left\{a^k, a^{k + 1}, \cdots, a^{k + d - 1}\right\}$
因为 $k, k + 1, \cdots, k + d - 1$ 是连续的 $d$ 个整数，它们除以 $d$ 的余数必定取遍 $0, 1, \cdots, d - 1$ 这 $d$ 个整数。因为 $a^k \equiv a^r$ ( $r$ 是 $k$ 除以 $d$ 的余数)，所以 $\left\{a^k, a^{k + 1}, \cdots, a^{k + d - 1}\right\}$ 就是 $\left\{a^0, a^1, \cdots, a^{d - 1}\right\}$，也就是 $\langle a \rangle$。

证明性质 5:

如果整数 $k$ 使得 $a^k \equiv 1 \pmod n$，那么必有 $d \mid k$（阶的整除性质）
利用带余除法，用 $k$ 除以 $d$：$k = d q + r (0 \le r \le d - 1)$
$a^k \equiv a^{d n + r} \equiv {(a^d)}^{n}\cdot a^r \equiv 1^n \cdot a^r \equiv a^r \equiv 1$
如果 $d$ 不整除 $k$，即 $r \gt 0$，那么 $r$ 就是一个满足 $a^r \equiv 1$ 的比 $d$ 更小的正整数，和 $d$ 是最小矛盾。
因此必有 $r = 0$，即 $d \mid k$。

设 $a$ 在模 $n$ 下的阶是 $d$。前面我们已经研究过，$1, a, a^2, \cdots, a^{d-1}$ 这 $d$ 个数在模 $n$ 下彼此不同，并且都与 $n$ 互素，我们知道，$0, 1, \cdots, n-1$ 中和 $n$ 互素的数一共有 $\varphi(n)$ 个（ $\varphi(n)$ 是欧拉函数，见「附录10」），所以 $a$ 的阶 $d$ 最多只能是 $\varphi(n)$。
那么 $d$ 能否取到 $\varphi(n)$ 呢？这是下一节要研究的问题。我们现在先证明阶的另一个重要性质：

『欧拉定理』：若 $\gcd(a, n) = 1$，则 $a^{\varphi(n)} \equiv 1 \pmod n$

「注1」：根据上面已经证明的「性质5」，欧拉定理如果成立，那么任何数 $a$ 的阶如果存在（即 $a$ 与 $n$ 互素时），都有 $\text{ord}_n(a) \mid \varphi(n)$

「注2」：如果欧拉定理成立，对于任意的素数 $p$，因为 $\varphi(p) = p - 1$，那么 $a^{\varphi(n)} = a^{p - 1} \equiv 1 \pmod p$，$a^p \equiv a \pmod p$，这正是「附录7」中的费马小定理。可见费马小定理是欧拉定理的特例。

现在证明欧拉定理：
在 $1$ 到 $n-1$ 中，找出所有与 $n$ 互素的整数，共有 $\varphi(n)$ 个，设它们为
$r_1, r_2, \dots, r_{\varphi(n)}$。考虑序列：
$a r_1, a r_2, \dots, a r_{\varphi(n)}$。
首先，它们两两模 $n$ 不同余。
反证法：若 $a r_i \equiv a r_j \pmod n$，则 $n \mid a(r_i - r_j)$。因为 $\gcd(a, n) = 1$，由欧几里得引理，必有 $n \mid (r_i - r_j)$。但 $\vert{}r_i - r_j\vert{} < n$，故 $r_i = r_j$。
其次，因为 $a$ 和 $r_i$ 都与 $n$ 互素，所以 $a r_i$ 也与 $n$ 互素。
因此，$a r_1, \dots, a r_{\varphi(n)}$ 模 $n$ 的结果，其实就是 $r_1, \dots, r_{\varphi(n)}$ 的一个重新排列。将它们全部乘起来：
$(a r_1) \cdot (a r_2) \dots (a r_{\varphi(n)}) \equiv r_1 \cdot r_2 \dots r_{\varphi(n)} \pmod n$
提取 $a$，得到
$a^{\varphi(n)} (r_1 \dots r_{\varphi(n)}) \equiv (r_1 \dots r_{\varphi(n)}) \pmod n$
因为每个 $r_i$ 都与 $n$ 互素，它们的乘积也与 $n$ 互素。由欧几里得引理（或者由前面「性质3」模乘法逆元存在），我们可以将乘积从同余式两边约去，得到 $a^{\varphi(n)} \equiv 1 \pmod n$。证明完毕。

既然 $\text{ord}_n(a)$ 最大只能是 $\varphi(n)$，那么有没有可能达到这个上限呢？
『原根』：如果一个整数 $g$ 满足 $\gcd(g, n) = 1$，且 $\text{ord}_n(g) = \varphi(n)$，我们就称 $g$ 为模 $n$ 的原根。

根据前面「阶的性质1」，如果 $g$ 是 $n$ 的原根，那么 $g, g^2, \cdots, g^{\varphi(n)}$ 恰好生成了 $1 \cdots n$ 中所有与 $n$ 互素的 $\varphi(n)$ 个数

并非所有数字都有原根（高斯在《算数研究》中证明了，只有 $2, 4, p^k, 2p^k$ 有原根，其中 $p$ 为奇素数）。我们不深入讨论存在性，这小节只证明：如果一个数 $n$ 存在原根，那么它一定恰好有 $\varphi(\varphi(n))$ 个不同的原根。

证明：既然存在一个原根 $g$，那么所有与 $n$ 互素的数都可以写成 $g^k$ ($1 \le k \le \varphi(n)$)。
我们考察 $g^k$ 的阶。设 $g^k$ 的阶为 $d$，则 $(g^k)^d \equiv 1 \pmod n \implies g^{kd} \equiv 1 \pmod n$。
由「阶的性质5」，$\varphi(n) \mid kd$。要让 $d$ 最小，$d$ 必须等于 $\frac{\varphi(n)}{\gcd(k, \varphi(n))}$。
$g^k$ 要成为原根，必须满足其阶 $d = \varphi(n)$，这当且仅当 $\gcd(k, \varphi(n)) = 1$。
在 $1$ 到 $\varphi(n)$ 之间，与 $\varphi(n)$ 互素的 $k$ 恰好有 $\varphi(\varphi(n))$ 个。证明完毕。

要找模 $n$ 的原根，穷举法是最直接的：
首先找出 $1\cdots n$ 中所有和 $n$ 互素的数（$\varphi(n)$个），逐个尝试。
假设 $g$ 是其中之一，如何快速判断 $g$ 是否为原根？只要保证 $g^k \not\equiv 1 \pmod n$ 对所有 $(k = \varphi(n)\text{ 的真因数})$ 都成立即可（这说明让 $g^k \equiv 1$ 的只能是 $\varphi(n)$）。我们找出 $\varphi(n)$ 的所有素因数 $q_1, q_2, \dots, q_k$。
因为整除传递性，只需要验证那几个“最大的真因数”（即 $\varphi(n)/q_i$），就能把所有更小的真因数一网打尽。即：
如果对于每一个素因数 $q_i$，都有 $g^{\varphi(n)/q_i} \not\equiv 1 \pmod n$，那么 $g$ 的阶不可能是 $\varphi(n)$ 的任何真因数，因此必定是 $\varphi(n)$，$g$ 就是原根。

前面提到过，形如 $2, 4, p^k, 2p^k$ 的数有原根（其中 $p$ 为奇素数），我们现在证明简化的版本，即 『任意素数都有原根』。

证明：设 $p$ 为素数，$\varphi(p) = p - 1$。

原根的“候选人”为 $1$ 到 $p - 1$ 这 $p - 1$ 个数。

我们对所有“候选人”按照它的阶分组，设阶恰好为 $d$ 的元素的个数为 $\psi(d)$。其中 $d$ 是 $\varphi(p)$ (即 $p - 1$ ) 的因数并且 $1 \le d \le p - 1$

如果 $\psi(d) > 0$，意味着至少存在一个元素 $a$，其阶为 $d$。

那么 $a^1, a^2, \dots, a^d$ 这 $d$ 个数两两不同余（「阶的性质1」），并且它们代入 $x^d$ 都有 $(a^k)^d = (a^d)^k \equiv 1^k \equiv 1 \pmod p$。也就是说它们是方程 $x^d \equiv 1 \pmod p$ 的 $d$ 个不同的根。

我们知道在模素数 $p$ 的多项式环中，次数为 $d$ 的多项式最多只有 $d$ 个根。这说明方程 $x^d \equiv 1 \pmod p$ 的所有根恰好就是这 $d$ 个数！（注：这段推理严格依赖 $p$ 是素数，只有 $p$ 是素数，$0, 1, \cdots, p - 1$ 才在模 $p$ 运算下构成一个数域，各种多项式定理才能用于模 $p$ 下的多项式，包括这里判断根的个数所依赖的多项式的因式定理。详见「附录6」）。

另一方面，我们知道如果一个“候选人”的阶为 $d$，它必须是 $x^d \equiv 1 \pmod p$ 的根。所以实际阶为 $d$ 的元素也只能从 $a^1, a^2, \dots, a^d$ 中选，它们是这些根中不存在更小的 $d'$ 使得 $x^{d'} \equiv 1 \pmod p$ 的元素。

既然阶为 $d$ 的元素只能从 $a^1, a^2, \dots, a^d$ 这 $d$ 个数中产生，我们现在就来考察这里面的任意一个元素 $a^k$（其中 $1 \le k \le d$），看看它的阶到底是多少。

设 $a^k$ 模 $p$ 的真实阶为 $m$。根据阶的定义，这意味着 $(a^k)^m \equiv 1 \pmod p$，也就是 $a^{km} \equiv 1 \pmod p$。

由前面证明过的「阶的性质5（整除性）」，既然 $a$ 的阶是 $d$，且 $a^{km} \equiv 1 \pmod p$，那么必定有：

$d \mid km$

我们将这个整除关系化简。设 $k$ 和 $d$ 的最大公约数为 $g = \gcd(k, d)$。将 $d$ 和 $k$ 同时除以 $g$，得到：

$\frac{d}{g} \mid \frac{k}{g} \cdot m$

因为 $\frac{d}{g}$ 和 $\frac{k}{g}$ 已经互素，根据欧几里得引理，$\frac{d}{g}$ 必定能整除 $m$。

要想让 $m$ 成为满足条件的最小正整数（这就是阶的定义），$m$ 必须等于 $\frac{d}{g}$。

所以，元素 $a^k$ 的真实阶 $m = \frac{d}{\gcd(k, d)}$。

我们要找的是阶恰好等于 $d$ 的元素，这就要求：$\frac{d}{\gcd(k, d)} = d$。

显然，这当且仅当 $\gcd(k, d) = 1$ 时才成立。

这意味着，在 $a^1, a^2, \dots, a^d$ 这 $d$ 个元素中，只有那些指数 $k$ 与 $d$ 互素的元素 $a^k$，它的阶才是 $d$。在 $1$ 到 $d$ 之间，与 $d$ 互素的整数个数，恰好就是欧拉函数的定义，即 $\varphi(d)$ 个！

至此我们得出一个严密的结论：只要假设 $\psi(d) > 0$（即至少存在一个阶为 $d$ 的元素），那么阶为 $d$ 的元素就必定恰好有 $\varphi(d)$ 个。

也就是说，对于任何 $d$，$\psi(d)$ 要么等于 $0$，要么等于 $\varphi(d)$。

最后，我们把所有因数 $d$ 统合起来。因为 $1$ 到 $p-1$ 这 $p-1$ 个数字中，每一个数都有唯一的一个阶 $d$，且由前面欧拉定理的推论「注1」可知，$d$ 必定是 $p-1$ 的因数。所以，如果我们把所有数字按阶来统计，总数必然等于 $p-1$：

$\sum_{d \mid p-1} \psi(d) = p - 1$

另一方面，根据「附录10」中的欧拉函数的因数和性质，有下面的公式：

$\sum_{d \mid p-1} \varphi(d) = p - 1$

对比这两个式子：因为每一个 $\psi(d)$ 要么是 $0$，要么是 $\varphi(d)$。如果存在哪怕一个 $d$ 使得 $\psi(d) = 0$，那么上面那个式子的总和就会严格小于下面那个式子的总和，这就不可能等于 $p-1$ 了！因此，唯一的可能是：所有的 $\psi(d)$ 都不能等于 0，必须统统等于 $\varphi(d)$。特别地，对于因数 $d = p - 1$，必定有：

$\psi(p-1) = \varphi(p-1) > 0$

这意味着，阶恰好为 $p-1$ 的元素必然存在。根据原根的定义，这就完美证明了模 $p$ 的原根必定存在！证明完毕。