原根
原根的存在性判别、构造与原根的个数。
定义
设 \(m\) 为正整数，\(a\) 为与 \(m\) 互素的整数。\(a\) 模 \(m\) 的阶定义为
\(\mathrm{ord}_m(a) = \min\{n \geq 1 : a^n \equiv 1 \pmod{m}\}\)
若 \(\mathrm{ord}_m(a) = \varphi(m)\)，则称 \(a\) 为模 \(m\) 的原根（primitive root）。
模 \(p\) 的原根存在性
定理：对任意素数 \(p\)，存在模 \(p\) 的原根。等价地，\((\mathbb{Z}/p\mathbb{Z})^\times\) 是循环群。
代数视角：有限 Abel 群与有限域 证明了更一般的结果——任何有限域 \(\mathbb{F}_q\) 的乘法群 \(\mathbb{F}_q^\times\) 都是循环群。\((\mathbb{Z}/p\mathbb{Z})^\times = \mathbb{F}_p^\times\) 是 \(q = p\) 的特例。那里用的是有限 Abel 群结构定理，而这里用分圆多项式给出了另一条证明路线。
证明：由 分圆多项式引理 4，\(\Phi_{p-1}(a) \equiv 0 \pmod{p}\) 推出 \(\mathrm{ord}_p(a) = p-1\)。\(\Phi_{p-1}(x)\) 是 \(p-1\) 次多项式，而 \(x^{p-1}-1 \equiv \prod_{a=1}^{p-1}(x-a) \pmod{p}\)（费马小定理），由基本分解 \(x^{p-1}-1 = \prod_{d \mid p-1} \Phi_d(x)\) 比较次数和根的结构，\(\Phi_{p-1}\) 模 \(p\) 必有根，这些根就是原根。
模素数幂的原根
奇素数的情形
定理：设 \(p\) 为奇素数，\(l \geq 1\)，则模 \(p^l\) 存在原根。
提升引理：若 \(g\) 是模 \(p\) 的原根且 \(g^{p-1} \not\equiv 1 \pmod{p^2}\)，则 \(g\) 是模 \(p^l\) 的原根（对所有 \(l \geq 1\)）。
关键计算（归纳法）：对 \(k \geq 1\)，
\((1 + ap)^{p^{k-1}} \equiv 1 + ap^k \pmod{p^{k+1}}\)
因此 \((1+ap)^{p^{l-1}(p-1)} \equiv 1 \pmod{p^l}\) 但 \(\not\equiv 1 \pmod{p^{l+1}}\)（当 \(p \nmid a\)）。
结合：若 \(g^{p-1} \equiv 1 \pmod{p^2}\)，则 \((g+p)^{p-1} \not\equiv 1 \pmod{p^2}\)，故总可找到满足条件的原根 \(g\)。
模 \(2^l\)（\(l \geq 3\)）的情形
定理：模 \(2^l\)（\(l \geq 3\)）没有原根。
模 \(2^l\) 的可逆元可表示为
\((-1)^a \cdot 5^b, \quad a \in \{0,1\},\; b \in \{0, 1, \ldots, 2^{l-2}-1\}\)
关键引理：\(5^{2^{l-3}} \equiv 1 + 2^{l-1} \pmod{2^l}\)（\(l \geq 3\)），因此 \(\mathrm{ord}_{2^l}(5) = 2^{l-2}\)。
\(5\) 是一个 ” 准原根 “——它的阶恰好为 \(\varphi(2^l)/2 = 2^{l-2}\)，乘以 \(\pm 1\) 的因子后遍历所有可逆元。
原根存在性的完全刻画
定理：模 \(m\) 存在原根，当且仅当 \(m\) 是以下形式之一：
- \(1, 2, 4\)
- \(p^l\)（\(p\) 为奇素数，\(l \geq 1\)）
- \(2p^l\)（\(p\) 为奇素数，\(l \geq 1\)）
证明思路：对其他形式的 \(m\)，利用 CRT 将 \(\varphi(m)\) 分解，证明任何可逆元的阶都严格小于 \(\varphi(m)\)。若 \(m\) 有两个不同的奇素因子（或 \(2^l\) 与奇素因子同时出现），则对任意 \(a\) 有 \(a^{\varphi(m)/2} \equiv 1 \pmod{m}\)。
高次同余方程的求解框架
问题
解 \(x^n \equiv a \pmod{m}\)。
第一步：CRT 约化
设 \(m = p_1^{e_1} \cdots p_r^{e_r}\)，原方程有解当且仅当 \(x^n \equiv a \pmod{p_i^{e_i}}\) 分别有解。
第二步：原根线性化（素数情形）
对 \(x^n \equiv a \pmod{p}\)，设 \(g\) 为原根。令 \(x \equiv g^k\)，\(a \equiv g^s\)，方程变为
\(nk \equiv s \pmod{p-1}\)
这是一个线性同余方程，有解当且仅当 \(\gcd(n, p-1) \mid s\)。若有解，则有 \(\gcd(n, p-1)\) 个解。
这个过程相当于取 ” 离散对数 “——原根 \(g\) 相当于对数的底。
模 \(2^l\) 高次方程
利用 \((-1)^a \cdot 5^b\) 的表示，转化为联立方程。当 \(n\) 为奇数时方程有唯一解；当 \(n\) 为偶数时需讨论 \(a \pmod{4}\) 的取值。
二平方和定理
定理：设素数 \(p \equiv 1 \pmod{4}\)，则 \(p\) 可以表示为两个整数的平方和。
证明：设 \(g\) 为模 \(p\) 的原根，则 \(g^{(p-1)/2} \equiv -1 \pmod{p}\)。取 \(a = g^{(p-1)/4}\)（因 \(4 \mid p-1\)），则
\(a^2 \equiv g^{(p-1)/2} \equiv -1 \pmod{p}\)
因此 \(p \mid a^2 + 1\)。结合之前的结论，\(p\) 可表示为两个平方和。
Dirichlet 定理的特殊情形（\(b=1\)）
定理：设 \(m \geq 2\)，则存在无穷多个素数 \(p \equiv 1 \pmod{m}\)。
证明：假设只有有限个 \(p_1, \ldots, p_r\)。令 \(N = p_1 \cdots p_r\)，考虑 \(\Phi_m(mN)\)。
由于 \(|mN - \zeta^k| \geq mN - 1 > 1\)（对每个本原单位根 \(\zeta^k\)），\(|\Phi_m(mN)| > 1\)，它有素因子 \(p\)。
由引理 4，\(\Phi_m(mN) \equiv 0 \pmod{p}\) 推出 \(\mathrm{ord}_p(mN) = m\)（若 \(p \nmid mN\)），从而 \(m \mid p-1\)。
验证 \(p\) 不是已有的素数 \(p_i\)：\(\Phi_m(mN) \equiv \Phi_m(0) \pmod{p_i}\)，而 \(\Phi_m(0) = \pm 1\)，故 \(p_i \nmid \Phi_m(mN)\)，矛盾。
这个证明类似欧几里得证明素数无穷多——构造新数然后取其素因子。