\(\S 4.3\) 二次互反律
定理 4（二次互反律 / Gauss）
设 \(p, q\) 是互不相同的奇素数，则
\[
\begin{gathered}
\mathbf{\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}}
\end{gathered}
\]
等价地：
\[
\left(\frac{p}{q}\right) = \begin{cases}
\ \ \left(\dfrac{q}{p}\right) & \text{若 } p \equiv 1 \pmod{4} \text{ 或 } q \equiv 1 \pmod{4} \\[10pt]
-\left(\dfrac{q}{p}\right) & \text{若 } p \equiv q \equiv 3 \pmod{4}
\end{cases}
\]
二次互反律被誉为"数论之钻"。它是计算勒让德符号的核心工具——结合补充律（\(\frac{-1}{p}\) 和 \(\frac{2}{p}\)），可以将任意 \(\left(\frac{n}{p}\right)\) 的计算不断"翻转"到更小的模数，直至可以直接判断。
证明（高斯引理法概要）
高斯引理：设 \(p\) 是奇素数，\(\gcd(a, p) = 1\)。考虑 \(\frac{p-1}{2}\) 个数
\[
a,\ 2a,\ 3a,\ \dots,\ \frac{p-1}{2}a
\]
将它们模 \(p\) 化为最小正剩余，设其中有 \(m\) 个大于 \(\frac{p}{2}\)，则
\[
\left(\frac{a}{p}\right) = (-1)^m
\]
有了高斯引理后，考察 \(\left(\frac{p}{q}\right)\) 和 \(\left(\frac{q}{p}\right)\) 各自的 \(m\) 值。通过计算格点数目可得：
\[
\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} \quad \square
\]
勒让德符号计算示例
例 1：判断 \(x^2 \equiv 14 \pmod{31}\) 是否有解。
\[ \begin{aligned} \left(\frac{14}{31}\right) &= \left(\frac{2}{31}\right)\left(\frac{7}{31}\right) \\ \left(\frac{2}{31}\right) &= 1 \quad (\because\ 31 \equiv -1 \pmod{8}) \\[4pt] \left(\frac{7}{31}\right) &= \left(\frac{31}{7}\right) \quad (\because\ 7 \equiv 3,\ 31 \equiv 3 \pmod{4},\ \text{两个 } 3 \text{ 翻转为 } -) \\ &= -\left(\frac{31 \bmod 7}{7}\right) = -\left(\frac{3}{7}\right) \\ &= -\left(\frac{7}{3}\right) = -\left(\frac{1}{3}\right) = -1 \end{aligned} \]故 \(\left(\frac{14}{31}\right) = 1 \cdot (-1) = -1\)，\(14\) 是模 \(31\) 的二次非剩余，无解。
例 2：判断 \(x^2 \equiv 15 \pmod{31}\) 是否有解。
\[ \begin{aligned} \left(\frac{15}{31}\right) &= \left(\frac{3}{31}\right)\left(\frac{5}{31}\right) \\ \left(\frac{3}{31}\right) &= -\left(\frac{31}{3}\right) = -\left(\frac{1}{3}\right) = -1 \\[4pt] \left(\frac{5}{31}\right) &= \left(\frac{31}{5}\right) = \left(\frac{1}{5}\right) = 1 \end{aligned} \]故 \(\left(\frac{15}{31}\right) = -1\)，\(15\) 是模 \(31\) 的二次非剩余，无解。