Appearance
二次剩余与阶（Quadratic Residues & Order）
核心定位
二次剩余研究模素数下的平方数分布规律，其核心工具勒让德符号与二次互反律被高斯誉为「数论的宝石」。阶与原根则是深入理解模乘法群结构的关键——原根的存在使得模运算中的乘法问题可以转化为加法（指数）问题。本笔记将这两个密切相关的话题系统展开，与 复数、整除与同余基础、数论函数与欧拉定理 形成完整的知识网络。
一、二次剩余的基本概念
1.1 定义
二次剩余与二次非剩余
设 $p$ 为奇素数，$\gcd(a, p) = 1$。若同余方程 $x^2 \equiv a \pmod p$有解，则称$a$是模$p$的二次剩余（Quadratic Residue）；否则称$a$是模$p$ 的二次非剩余（Quadratic Non-Residue）。
基本事实
模奇素数 $p$的缩剩余系$\lbrace 1, 2, \dots, p-1\rbrace $中，恰有$\frac{p-1}{2}$个二次剩余和$\frac{p-1}{2}$个二次非剩余。这是因为$1^2, 2^2, \dots, ((p-1)/2)^2$模$p$ 两两不同余且涵盖了所有二次剩余。
二、勒让德符号
2.1 定义
勒让德符号（Legendre Symbol）
设 $p$ 为奇素数，定义： $$\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{若 } a \text{ 是模 } p \text{ 的二次剩余且 } p \nmid a \newline -1 & \text{若 } a \text{ 是模 } p \text{ 的二次非剩余} \newline 0 & \text{若 } p \mid a \end{cases}$$
2.2 基本性质
勒让德符号的运算法则
- 乘法性质：$\displaystyle\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)$
- 平方数：$\displaystyle\left(\frac{a^2}{p}\right) = 1$（当 $p \nmid a$）
- 周期性质：若 $a \equiv b \pmod p$，则 $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
- $-1$ 的符号：$\displaystyle\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$
- $2$ 的符号：$\displaystyle\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}$
性质 4 的含义：$-1$是模$p$的二次剩余当且仅当$p \equiv 1 \pmod 4$。例如 $-1 \equiv 2^2 \pmod 5$（$5 \equiv 1 \pmod 4$），但 $-1$不是模$7$ 的二次剩余（$7 \equiv 3 \pmod 4$）。
性质 5 的含义：$2$是模$p$的二次剩余当且仅当$p \equiv \pm 1 \pmod 8$。
三、欧拉判别法
欧拉判别法（Euler's Criterion）
设 $p$ 为奇素数，$p \nmid a$，则： $$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p$$
证明：由费马小定理，$(a^{(p-1)/2})^2 \equiv a^{p-1} \equiv 1 \pmod p$，故 $a^{(p-1)/2} \equiv \pm 1 \pmod p$。若 $a$是二次剩余，设$a \equiv x^2$，则 $a^{(p-1)/2} \equiv x^{p-1} \equiv 1 \pmod p$。由于模 $p$的二次剩余和非剩余各占一半，且多项式$x^{(p-1)/2} - 1 \equiv 0$最多有$(p-1)/2$个根，故二次非剩余必满足$a^{(p-1)/2} \equiv -1 \pmod p$。
实际应用
欧拉判别法提供了计算勒让德符号的算法途径，但当 $p$很大时计算$a^{(p-1)/2} \bmod p$ 效率不高。搭配二次互反律使用更高效。
四、二次互反律
二次互反律（Law of Quadratic Reciprocity）
设 $p, q$ 为不同的奇素数，则： $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$$
语言表述
若 $p$与$q$中至少有一个是$4k+1$型的素数，则$p$是模$q$的二次剩余当且仅当$q$是模$p$的二次剩余（即$\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$）。若两者都是 $4k+3$型，则$\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$。
综合计算方法：结合勒让德符号的乘法性质、$(-1/p)$和$(2/p)$的公式，再加上二次互反律，可以将任意$\left(\frac{a}{p}\right)$ 的计算递归地化简到小素数。
五、阶（Order）
5.1 定义与基本性质
阶（Order）
设 $\gcd(a, m) = 1$。满足 $a^d \equiv 1 \pmod m$的最小正整数$d$称为$a$模$m$的阶，记作$\operatorname{ord}_m(a)$。
阶的核心性质
- 整除 $\varphi(m)$：$\operatorname{ord}_m(a) \mid \varphi(m)$。特别地，对于素数 $p$，$\operatorname{ord}_p(a) \mid (p-1)$。
- 充要条件：$a^k \equiv 1 \pmod m$当且仅当$\operatorname{ord}_m(a) \mid k$。
- 幂的阶：$\operatorname{ord}_m(a^k) = \dfrac{\operatorname{ord}_m(a)}{\gcd(\operatorname{ord}_m(a),\thinspace k)}$。
- 乘积的阶：若 $\gcd(\operatorname{ord}_m(a), \operatorname{ord}_m(b)) = 1$，则 $\operatorname{ord}_m(ab) = \operatorname{ord}_m(a) \cdot \operatorname{ord}_m(b)$。
性质 1 的证明：由欧拉定理 $a^{\varphi(m)} \equiv 1 \pmod m$。令 $d = \operatorname{ord}_m(a)$，用带余除法 $\varphi(m) = dq + r$（$0 \le r < d$），则 $a^r \equiv a^{\varphi(m) - dq} \equiv 1 \pmod m$。由 $d$的最小性知$r = 0$，故 $d \mid \varphi(m)$。
六、原根
6.1 定义
原根（Primitive Root）
若 $\operatorname{ord}_m(g) = \varphi(m)$，则称 $g$为模$m$的原根。此时$\lbrace g^0, g^1, \dots, g^{\varphi(m)-1}\rbrace $构成模$m$ 的缩剩余系。
原根的意义在于：模乘法群成为循环群，乘法问题可转化为加法（指数）。任何与 $m$互素的数$a$可唯一表示为$a \equiv g^{\operatorname{ind}_g(a)} \pmod m$，其中 $\operatorname{ind}_g(a)$称为$a$以$g$ 为底的指数（或离散对数）。
6.2 原根的存在性
原根存在定理
模 $m$存在原根当且仅当$m = 1, 2, 4, p^k, 2p^k$，其中 $p$ 为奇素数，$k \ge 1$。
特别地：
- 每个素数 $p$都有原根，且恰有$\varphi(p-1)$ 个原根。
- 模 $p$的原根也是模$p^k$和$2p^k$ 的原根（经适当选取）。
6.3 离散对数（指数）
指数（Index / Discrete Logarithm）
设 $g$是模$m$的原根，对$\gcd(a, m) = 1$，定义 $\operatorname{ind}_g(a)$为满足$g^x \equiv a \pmod m$的最小非负整数$x$（$0 \le x < \varphi(m)$）。
指教满足类似对数的运算法则：
- $\operatorname{ind}_g(ab) \equiv \operatorname{ind}_g(a) + \operatorname{ind}_g(b) \pmod{\varphi(m)}$
- $\operatorname{ind}_g(a^k) \equiv k \cdot \operatorname{ind}_g(a) \pmod{\varphi(m)}$
这使得解高次同余方程 $x^k \equiv a \pmod p$转化为线性同余方程$k \cdot \operatorname{ind}_g(x) \equiv \operatorname{ind}_g(a) \pmod{p-1}$。
七、典型例题
例 1：判断二次剩余
判断 $-1$是模哪些小于$20$ 的奇素数的二次剩余。
解：$-1$是二次剩余$\iff p \equiv 1 \pmod 4$。小于 $20$ 的奇素数：$3, 5, 7, 11, 13, 17, 19$。其中 $p \equiv 1 \pmod 4$的有$5, 13, 17$。验证：$2^2 = 4 \equiv -1 \pmod 5$；$5^2 = 25 \equiv -1 \pmod{13}$；$4^2 = 16 \equiv -1 \pmod{17}$。✅
例 2：欧拉判别法
用欧拉判别法判断 $3$是模$7$ 的二次剩余还是二次非剩余。
解：$p = 7$，$(p-1)/2 = 3$。计算 $3^3 = 27 \equiv 6 \equiv -1 \pmod 7$。故 $\left(\frac{3}{7}\right) = -1$，$3$是模$7$ 的二次非剩余。验证：$1^2=1, 2^2=4, 3^2=9\equiv 2, 4^2=16\equiv 2, 5^2=25\equiv 4, 6^2=36\equiv 1$，确实没有模 $7$平方余$3$ 的数。
例 3：二次互反律
利用二次互反律计算 $\left(\dfrac{2}{p}\right)$的一般公式，并判断$2$是模$13$ 的二次剩余吗？
解：由公式 $\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}$。$13^2 - 1 = 168$，$168/8 = 21$为奇数，故$\left(\frac{2}{13}\right) = -1$，$2$不是模$13$的二次剩余。验证：平方数为$1, 4, 9, 3, 12, 10$，确无 $2$。
另法用二次互反律和欧拉判别法综合：$\left(\frac{13}{2}\right) = \left(\frac{1}{2}\right) = 1$，而 $p=13 \equiv 1 \pmod 4$，$q=2$ 需特殊处理（$2$是偶素数），故优先使用$(2/p)$ 公式。
例 4：求阶
求 $\operatorname{ord}_{13}(5)$。
解：$\varphi(13) = 12$，阶必为 $12$ 的因子：$1, 2, 3, 4, 6, 12$。逐一检验： $5^1 = 5 \not\equiv 1$；$5^2 = 25 \equiv -1 \pmod{13}$（并非 $1$）；由于 $5^2 \equiv -1$，$5^4 \equiv 1 \pmod{13}$。故 $\operatorname{ord}_{13}(5) = 4$。验证：$5^4 = 625 = 13 \times 48 + 1 \equiv 1 \pmod{13}$。✅
例 5：求原根
求模 $7$ 的所有原根。
解：$\varphi(7) = 6$，原根的阶必须为 $6$。检验 $1$到$6$：
- $1$：阶 $1$ ❌
- $2$：$2^2=4$，$2^3=8\equiv 1$，阶 $3$ ❌
- $3$：$3^2=9\equiv 2$，$3^3\equiv 6\equiv -1$，$3^6\equiv 1$，且 $3^1, 3^2, 3^3$皆$\not\equiv 1$，故阶为 $6$ ✅
- $4$：$4^2=16\equiv 2$，$4^3\equiv 8\equiv 1$，阶 $3$ ❌
- $5$：$5 \equiv -2$，阶与 $2$相同为$3$ ❌
- $6 \equiv -1$：阶 $2$ ❌
故模 $7$的唯一原根是$3$（以及 $5$的原根数目为$\varphi(6) = 2$，检验 $5$：$5^2=25\equiv 4$，$5^3\equiv 20\equiv 6\equiv -1$，$5^6\equiv 1$，阶也为 $6$✅）。模$7$的原根为$3$和$5$。
例 6：指数求解同余方程
利用原根 $3$（模 $7$）解同余方程 $x^3 \equiv 6 \pmod 7$。
解：以 $3$ 为底建指数表：$3^0=1, 3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5$。方程 $x^3 \equiv 6$化为$3 \cdot \operatorname{ind}_3(x) \equiv \operatorname{ind}_3(6) = 3 \pmod 6$。即 $3 \cdot \operatorname{ind}_3(x) \equiv 3 \pmod 6 \implies \operatorname{ind}_3(x) \equiv 1, 3, 5 \pmod 6$。对应 $x \equiv 3^1=3, 3^3=6, 3^5=5 \pmod 7$。验证：$3^3=27\equiv 6$，$6^3=216\equiv 6$（$216=7\times 30+6$），$5^3=125\equiv 6$（$125=7\times 17+6$）。✅
八、雅可比符号
雅可比符号（Jacobi Symbol）
设 $n$ 为正奇数，$n = p_1 p_2 \cdots p_k$（允许重复，即素因子幂次展开后视作若干素数之积）。对整数 $a$，定义： $$\left(\frac{a}{n}\right) = \prod_{i=1}^{k} \left(\frac{a}{p_i}\right)$$ 当 $n$ 为素数时，雅可比符号退化为勒让德符号。
与勒让德符号的关键区别：
- 雅可比符号取值为 $\pm 1$时，不能判断$a$是否为模$n$的二次剩余（除非$n$ 为素数）
- 若 $\left(\frac{a}{n}\right) = -1$，则 $a$必为模$n$ 的二次非剩余
- 若 $\left(\frac{a}{n}\right) = 1$，$a$可能是二次剩余，也可能不是（如$\left(\frac{2}{9}\right) = \left(\frac{2}{3}\right)^2 = 1$，但 $2$不是模$9$ 的二次剩余）
雅可比符号的运算法则
设 $n$ 为正奇数：
- 完全积性：$\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$
- 同余不变：若 $a \equiv b \pmod n$，则 $\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right)$
- 互反律（雅可比符号版本）：若 $m, n$ 为互素的正奇数，则： $$\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}$$
- $-1$与$2$ 的公式： $$\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}},\qquad \left(\frac{2}{n}\right) = (-1)^{\frac{n^2-1}{8}}$$
为何引入雅可比符号？
雅可比符号允许在模合数的情况下递归使用互反律，不必先分解 $n$。这是计算勒让德符号时的重要加速技巧——直接用雅可比符号计算 $\left(\frac{a}{p}\right)$（其中 $p$ 为素数）等同于勒让德符号，但避免了中间过程对素数的需求。
雅可比符号计算
计算 $\left(\frac{7}{45}\right)$。
解：$45 = 9 \times 5 = 3^2 \times 5$。$\left(\frac{7}{45}\right) = \left(\frac{7}{3}\right)^2 \cdot \left(\frac{7}{5}\right)$。$7 \equiv 1 \pmod 3$，故 $\left(\frac{7}{3}\right) = \left(\frac{1}{3}\right) = 1$。$7 \equiv 2 \pmod 5$，$\left(\frac{2}{5}\right) = (-1)^{(25-1)/8} = (-1)^3 = -1$。故 $\left(\frac{7}{45}\right) = 1 \cdot (-1) = -1$。即 $7$是模$45$ 的二次非剩余。
九、克罗内克符号
克罗内克符号（Kronecker Symbol）
推广雅可比符号至偶数和负数底：
- $\left(\frac{a}{2}\right) = \begin{cases} 0 & 2 \mid a \newline 1 & a \equiv \pm 1 \pmod 8 \newline -1 & a \equiv \pm 3 \pmod 8 \end{cases}$
- $\left(\frac{a}{-1}\right) = \operatorname{sgn}(a)$（即 $a > 0$取$1$，$a < 0$取$-1$）
- $\left(\frac{a}{0}\right) = \begin{cases} 1 & a = \pm 1 \newline 0 & \text{否则}\end{cases}$
- 对一般 $n = 2^k \cdot m$（$m$ 奇），$\left(\frac{a}{n}\right) = \left(\frac{a}{2}\right)^k \left(\frac{a}{m}\right)$
克罗内克符号是二次剩余理论中最一般的符号系统，在二次型理论与类域论中起基础作用。
十、二次剩余的进一步性质
10.1 二次剩余的乘法结构
二次剩余乘法群
设 $p$为奇素数。模$p$的二次剩余集合$QR_p$与二次非剩余集合$NQR_p$ 满足：
- $QR_p \cdot QR_p = QR_p$
- $QR_p \cdot NQR_p = NQR_p$
- $NQR_p \cdot NQR_p = QR_p$
即 $QR_p$是模$p$缩剩余系的指数为$2$的子群（大小$(p-1)/2$），商群同构于 $\lbrace \pm 1\rbrace $。
10.2 二次剩余计数
重要求和公式
- $\displaystyle\sum_{a=1}^{p-1} \left(\frac{a}{p}\right) = 0$（剩余与非剩余各半）
- 二次剩余的和：$\displaystyle\sum_{\substack{1 \le a \le p-1 \newline a \in QR_p}} a = \dfrac{p(p-1)}{4}$当$p \equiv 1 \pmod 4$
- 剩余与非剩余计数：$\#\lbrace a : 1 \le a \le n, a \in QR_p\rbrace = \dfrac{n}{2} + O(\sqrt{p})$
10.3 二次互反律的推广：高斯互反律
高斯引理的一般化
设 $a$ 奇，$n$ 正奇数，$\gcd(a, n) = 1$。考虑 $a, 2a, \dots, \frac{n-1}{2} a \pmod n$的最小正剩余中大于$\frac{n}{2}$的个数$\mu(a, n)$，则： $$\left(\frac{a}{n}\right) = (-1)^{\mu(a, n)}$$
十一、高次剩余简介
$k$ 次剩余
设 $p$ 为素数，$k \mid p - 1$，$\gcd(a, p) = 1$。若 $x^k \equiv a \pmod p$有解，称$a$为模$p$的$k$ 次剩余。
判定准则：设 $g$为模$p$的原根，则$a = g^i$是$k$次剩余$\iff \gcd(k, p-1) \mid i$。
$k$ 次剩余的个数
模 $p$的$k$次剩余（含$1$）共有 $\dfrac{p - 1}{\gcd(k, p-1)}$ 个。
Euler $k$ 次剩余判定
设 $k \mid p - 1$，$a$是$k$次剩余$\iff a^{(p-1)/\gcd(k,p-1)} \equiv 1 \pmod p$。
三次剩余
当 $p \equiv 1 \pmod 3$ 时，$a$是模$p$的三次剩余$\iff a^{(p-1)/3} \equiv 1 \pmod p$，此时恰有 $(p-1)/3$ 个三次剩余。
十二、阶的进一步性质
阶的乘积公式
设 $\operatorname{ord}_m(a) = r$，$\operatorname{ord}_m(b) = s$。
- 若 $\gcd(r, s) = 1$，则 $\operatorname{ord}_m(ab) = rs$
- 一般地：$\operatorname{ord}_m(ab) \mid \operatorname{lcm}(r, s)$，且 $\operatorname{lcm}(r, s) / \gcd(r, s) \mid \operatorname{ord}_m(ab)$ 不一定成立
阶的存在性定理
对任意 $\gcd(a, m) = 1$，$a$模$m$的阶必为$\varphi(m)$的因子。对所有$a$取遍最小阶，得到$m$的"原子阶"，原根存在当且仅当存在$a$使$\operatorname{ord}_m(a) = \varphi(m)$。
阶与原根的关系
设 $g$是模$m$的原根，则模$m$的所有原根恰为$\lbrace g^k : \gcd(k, \varphi(m)) = 1\rbrace $，共有 $\varphi(\varphi(m))$ 个。
十三、典型例题（进阶）
例 7：雅可比符号加速计算
计算 $\left(\frac{1873}{2011}\right)$（$2011$ 为素数）。
解：用雅可比符号互反律递推（无需分解 $1873$）。$2011 \equiv 3 \pmod 4$，$1873 \equiv 1 \pmod 4$。 $$\left(\frac{1873}{2011}\right) = \left(\frac{2011}{1873}\right) = \left(\frac{138}{1873}\right) = \left(\frac{2}{1873}\right)\left(\frac{69}{1873}\right)$$ $1873 \equiv 1 \pmod 8$，故 $\left(\frac{2}{1873}\right) = 1$。 $69 \equiv 1 \pmod 4$，故 $\left(\frac{69}{1873}\right) = \left(\frac{1873}{69}\right) = \left(\frac{10}{69}\right) = \left(\frac{2}{69}\right)\left(\frac{5}{69}\right)$。 $69 \equiv 5 \pmod 8$，$\left(\frac{2}{69}\right) = -1$。 $69 \equiv 1 \pmod 4$，$\left(\frac{5}{69}\right) = \left(\frac{69}{5}\right) = \left(\frac{4}{5}\right) = 1$。 故 $\left(\frac{69}{1873}\right) = -1 \cdot 1 = -1$，最终 $\left(\frac{1873}{2011}\right) = 1 \cdot (-1) = -1$。即 $1873$是模$2011$ 的二次非剩余。
例 8：高次剩余判定
判断 $2$是否为模$17$的$4$ 次剩余。
解：$p = 17$，$k = 4$，$p - 1 = 16$，$\gcd(k, p-1) = 4$。判定准则：$a^{(p-1)/4} \equiv 1 \pmod p \iff a^{4} \equiv 1 \pmod{17}$。计算 $2^4 = 16 \equiv -1 \not\equiv 1 \pmod{17}$，故 $2$不是模$17$的$4$次剩余。然而$\left(\frac{2}{17}\right) = (-1)^{(289-1)/8} = (-1)^{36} = 1$，故 $2$是二次剩余但非$4$次剩余（这能存在，因为$4$ 次剩余是二次剩余的子集）。
例 9：阶与原根
设 $p = 41$。求模 $p$ 的所有原根的个数，并求一个原根。
解：$\varphi(41) = 40 = 2^3 \cdot 5$。原根个数 $= \varphi(40) = \varphi(8)\varphi(5) = 4 \cdot 4 = 16$。 寻找一个原根：试 $a = 6$。$40$的素因子为$2, 5$，需验证 $6^{40/2} = 6^{20} \not\equiv 1 \pmod{41}$与$6^{40/5} = 6^8 \not\equiv 1 \pmod{41}$。 $6^2 = 36 \equiv -5 \pmod{41}$，$6^4 \equiv 25$，$6^8 \equiv 625 \equiv 625 - 41 \cdot 15 = 625 - 615 = 10 \not\equiv 1$ ✓。 $6^{20} = (6^4)^5 \equiv 25^5$。$25^2 \equiv 625 \equiv 10$，$25^4 \equiv 100 \equiv 100 - 82 = 18$，$25^5 \equiv 18 \cdot 25 = 450 \equiv 450 - 41 \cdot 10 = 40 \equiv -1 \not\equiv 1$ ✓。 故 $6$是模$41$ 的原根。
例 10：原根与离散对数
以 $6$为原根（模$41$），求 $\operatorname{ind}_6(5)$。
解：依次计算 $6^k \pmod{41}$：$6^1 = 6, 6^2 \equiv 36 \equiv -5, 6^3 \equiv -30 \equiv 11, 6^4 \equiv 66 \equiv 25, 6^5 \equiv 150 \equiv 150 - 3 \cdot 41 = 27, 6^6 \equiv 162 \equiv 162 - 3 \cdot 41 = 39 \equiv -2, 6^7 \equiv -12 \equiv 29, 6^8 \equiv 174 \equiv 174 - 4 \cdot 41 = 10$，$6^9 \equiv 60 \equiv 19$，$6^{10} \equiv 114 \equiv 32$，$6^{11} \equiv 192 \equiv 192 - 4 \cdot 41 = 28$，$6^{12} \equiv 168 \equiv 4$，$6^{13} \equiv 24$，$6^{14} \equiv 144 \equiv 21$，$6^{15} \equiv 126 \equiv 3$，$6^{16} \equiv 18$，$6^{17} \equiv 108 \equiv 26$，$6^{18} \equiv 156 \equiv 33$，$6^{19} \equiv 198 \equiv 34$，$6^{20} \equiv 204 \equiv -1$，$6^{21} \equiv -6 \equiv 35$，$6^{22} \equiv -36 \equiv 5$✓。故$\operatorname{ind}_6(5) = 22$。
例 11：原根不存在的情形
证明模 $8$ 没有原根。
证：$\varphi(8) = 4$。模 $8$缩剩余系为$\lbrace 1, 3, 5, 7\rbrace $。各数阶：$\operatorname{ord}_8(1) = 1$，$\operatorname{ord}_8(3) = 2$（$3^2 = 9 \equiv 1$），$\operatorname{ord}_8(5) = 2$，$\operatorname{ord}_8(7) = 2$。最大阶为 $2$，远小于 $\varphi(8) = 4$，故无原根。
例 12：互反律综合应用
设 $p, q$ 均为奇素数，$p \equiv q \equiv 3 \pmod 4$。证明：$\left(\frac{p}{q}\right) = -1$时$q$是模$p$ 的二次剩余。
证：由二次互反律，$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} = (-1)^{\text{奇}\cdot\text{奇}} = -1$。故 $\left(\frac{q}{p}\right) = -\left(\frac{p}{q}\right)^{-1} = -\left(\frac{p}{q}\right) = -(-1) = 1$，即 $q$是模$p$ 的二次剩余。
十四、原根与离散对数计算
离散对数问题（DLP）
给定原根 $g$和$a$（$\gcd(a, p) = 1$），求 $x$使$g^x \equiv a \pmod p$。这是现代密码学（如 Diffie-Hellman）的安全基础。
算法：
- 暴力：$O(p)$ 时间枚举
- Shank's Baby-step Giant-step：$O(\sqrt{p})$ 时间与空间
- Pohlig-Hellman：当 $p - 1$ 是光滑数时高效
- Index Calculus：亚指数算法 $L_p[1/2, c]$
十五、知识链接
- 复数 — 单位根在复数域中的性质与原根在模 $p$ 下的性质高度类似，均体现循环群的结构
- 整除与同余基础 — 费马小定理是阶理论的起点（阶必整除 $p-1$）
- 数论函数与欧拉定理 — 欧拉函数 $\varphi(m)$ 给出阶的上界与原根的定义域
- 不定方程与丢番图方程 — 利用二次剩余可判断 $x^2 \equiv a \pmod p$ 的可解性
- 排列组合 — 二次剩余计数与配对原理的运用