如何简洁地证明二次互反律？有哪些具体应用？

二次互反律的简洁证明与具体应用

二次互反律，一个在数论领域闪耀的明珠，它以一种近乎优雅的方式揭示了 Legendre 符号之间的深刻联系。虽然它的证明充满智慧和技巧，但我们可以尝试用一种相对简洁且易于理解的方式来阐释其核心思想，并探讨它在数学和密码学中的具体应用。

什么是二次互反律？

首先，我们需要明确一些基本概念。

二次剩余 (Quadratic Residue): 给定一个整数 $p$（通常为奇素数）和一个整数 $a$（不被 $p$ 整除），如果同余方程 $x^2 equiv a pmod{p}$ 有解，那么我们称 $a$ 是模 $p$ 的二次剩余。否则，如果无解，则称 $a$ 是模 $p$ 的二次非剩余。
Legendre 符号: Legendre 符号 $left(frac{a}{p} ight)$ 用来表示 $a$ 是模 $p$ 的二次剩余的性质。
如果 $a equiv 0 pmod{p}$，则 $left(frac{a}{p} ight) = 0$。
如果 $a$ 是模 $p$ 的二次剩余，则 $left(frac{a}{p} ight) = 1$。
如果 $a$ 是模 $p$ 的二次非剩余，则 $left(frac{a}{p} ight) = 1$。

Legendre 符号具有一些基本的性质：

1. 如果 $a equiv b pmod{p}$，则 $left(frac{a}{p} ight) = left(frac{b}{p} ight)$。
2. $left(frac{ab}{p} ight) = left(frac{a}{p} ight)left(frac{b}{p} ight)$。
3. $left(frac{a^2}{p} ight) = 1$，当 $p mid a$ 时。

有了这些基础，我们就可以进入二次互反律本身了。

二次互反律的简洁证明思想

二次互反律是关于两个不同奇素数 $p$ 和 $q$ 的 Legendre 符号 $left(frac{p}{q} ight)$ 和 $left(frac{q}{p} ight)$ 之间关系的定理。它可以用以下公式表示：

$$
left(frac{p}{q} ight) left(frac{q}{p} ight) = (1)^{frac{(p1)}{2}frac{(q1)}{2}}
$$

或者更常用的形式是：

$$
left(frac{p}{q} ight) = left(frac{q}{p} ight) (1)^{frac{(p1)}{2}frac{(q1)}{2}}
$$

这意味着，除非 $p$ 和 $q$ 都形如 $4k+3$，否则 $left(frac{p}{q} ight) = left(frac{q}{p} ight)$，即它们相等。如果 $p equiv 3 pmod{4}$ 且 $q equiv 3 pmod{4}$，那么 $left(frac{p}{q} ight) = left(frac{q}{p} ight)$，它们互为相反数。

证明二次互反律的方法有很多种，其中一些更为简洁且富有启发性的思路通常依赖于 高斯引理 (Gauss's Lemma)。高斯引理本身也是一个重要的工具，它的一个版本是这样表述的：

高斯引理 (版本一): 设 $p$ 是一个奇素数，整数 $a$ 与 $p$ 互素。考虑整数集合 $S = {a, 2a, 3a, dots, frac{p1}{2}a}$。将这些数对 $p$ 取模，得到剩余集合 ${r_1, r_2, dots, r_{frac{p1}{2}}}$。其中，这些剩余数 $r_i$ 都不为 $0$，且 $r_i otequiv r_j pmod{p}$ 当 $i eq j$ 时。令 $N$ 为在这些剩余数中，大于 $p/2$ 的数的个数。那么，
$$
left(frac{a}{p} ight) = (1)^N
$$

高斯引理的证明思路是：考虑集合 ${a, 2a, dots, frac{p1}{2}a}$ 模 $p$ 的剩余，这些剩余在 ${1, 2, dots, p1}$ 中。将这些剩余分为两类：小于 $p/2$ 的和大于 $p/2$ 的。显然，小于 $p/2$ 的数和大于 $p/2$ 的数在模 $p$ 下是不一样的。

现在，我们尝试利用高斯引理来证明二次互反律。我们需要证明：
$$
left(frac{q}{p} ight) = left(frac{p}{q} ight) (1)^{frac{(p1)}{2}frac{(q1)}{2}}
$$

让我们集中证明 $left(frac{q}{p} ight)$ 的表达式。根据高斯引理，我们考虑集合 $S_q = {q, 2q, 3q, dots, frac{p1}{2}q}$ 模 $p$ 的剩余。设 $N_q$ 是这些剩余中大于 $p/2$ 的数的个数。那么，
$$
left(frac{q}{p} ight) = (1)^{N_q}
$$

现在，我们要把 $N_q$ 与 $left(frac{p}{q} ight)$ 联系起来。这是最巧妙的一步，我们观察集合 $S_q$ 中的每个元素 $kq pmod p$ 的形式。

考虑集合 ${1, 2, dots, p1}$。我们用 $p$ 来分组这些数。对于任意一个整数 $x$， $x$ 和 $px$ 模 $p$ 的剩余是不同的。

设 $P = {1, 2, dots, frac{p1}{2}}$ 和 $Q = {frac{p+1}{2}, dots, p1}$。
那么 ${1, 2, dots, p1} = P cup Q$。
对于 $x in P$，我们有 $px in Q$。

现在我们来看集合 $S_q = {q, 2q, dots, frac{p1}{2}q}$。
将 $S_q$ 中的元素对 $p$ 取模，得到 ${r_1, r_2, dots, r_{frac{p1}{2}}}$。
我们统计这些 $r_i$ 中大于 $p/2$ 的个数 $N_q$。

考虑集合 ${1, 2, dots, frac{p1}{2}}$。
我们考察 $kq$ 模 $p$ 的剩余。
记 $kq equiv r_k pmod p$，其中 $1 le r_k le p1$。
我们把 $r_k$ 分为两类：
1. $r_k le frac{p1}{2}$ (属于 $P'={1, 2, dots, frac{p1}{2}}$ 模 $p$ 的剩余)
2. $r_k > frac{p1}{2}$ (属于 $Q'={frac{p+1}{2}, dots, p1}$ 模 $p$ 的剩余)

$N_q$ 就是第二类元素的个数。

现在，将这个思路推广到另一个方向。考虑集合 ${1, 2, dots, q1}$。我们关注的是 $p$ 作为模数，考察 $q$ 的二次剩余性。

另一个更“对称”的证明方法是利用 欧拉判别法 (Euler's Criterion)：
$$
left(frac{a}{p} ight) equiv a^{frac{p1}{2}} pmod{p}
$$

将欧拉判别法应用于 $left(frac{q}{p} ight)$ 和 $left(frac{p}{q} ight)$：
$$
left(frac{q}{p} ight) equiv q^{frac{p1}{2}} pmod{p}
$$
$$
left(frac{p}{q} ight) equiv p^{frac{q1}{2}} pmod{q}
$$

现在问题是如何连接 $q^{frac{p1}{2}}$ 和 $p^{frac{q1}{2}}$。这通常需要一些代数的技巧，例如计算一个特定的指数和或者一个多项式的值。

一个相当简洁且直观的证明是基于对一个特定集合的计数。考虑所有形如 $aq+bp$ 的表达式，其中 $a, b$ 是整数。

为了更深入地理解证明思路，我们转向一个更具“组合”色彩的证明。

基于计数的证明思路：

考虑所有满足 $1 le x le frac{p1}{2}$ 和 $1 le y le frac{q1}{2}$ 的整数对 $(x, y)$。
我们对 $qx py$ 的符号进行分类。

考虑一个二元函数 $f(x, y) = qx py$.
我们将 $x$ 从 $1$ 到 $frac{p1}{2}$ 变化，$y$ 从 $1$ 到 $frac{q1}{2}$ 变化。
总共有 $frac{p1}{2} imes frac{q1}{2}$ 对这样的 $(x, y)$。

我们将这些对 $(x, y)$ 按照 $qx py$ 的符号分类：
1. $qx py > 0 implies qx > py implies frac{x}{y} > frac{p}{q}$
2. $qx py < 0 implies qx < py implies frac{x}{y} < frac{p}{q}$
3. $qx py = 0 implies qx = py implies frac{x}{y} = frac{p}{q}$

由于 $p$ 和 $q$ 是素数且 $x le frac{p1}{2}$, $y le frac{q1}{2}$，所以 $qx le qfrac{p1}{2}$ 且 $py le pfrac{q1}{2}$。
若 $qx = py$，则 $p|qx$ 且 $q|py$。由于 $p, q$ 是素数且互素，所以 $p|x$ 且 $q|y$。
但是 $1 le x le frac{p1}{2}$，$1 le y le frac{q1}{2}$，这意味着 $p$ 不能整除 $x$， $q$ 也不能整除 $y$。
因此，$qx py$ 永远不会等于 $0$。

所以，所有的 $frac{p1}{2} imes frac{q1}{2}$ 对 $(x, y)$ 都满足 $qx py > 0$ 或 $qx py < 0$。

我们现在将注意力集中在 $frac{x}{y}$ 的比值上。
考虑集合 $A = {frac{x}{y} mid 1 le x le frac{p1}{2}, 1 le y le frac{q1}{2}}$。

对于每一个 $(x, y)$，我们考虑另一个对 $(x', y')$。
令 $x' = frac{px}{2}$ and $y' = frac{qy}{2}$ 似乎不是一个好的方向。

我们考虑一个更巧妙的配对方法。
对于任意一个 $x in {1, 2, dots, frac{p1}{2}}$, 我们考虑 $qx pmod{p}$.
令 $qx = k p + r$, 其中 $0 le r < p$.
我们关心的是 $r$ 的符号，以及 $r$ 与 $p/2$ 的关系。

高斯的一个巧妙证明（基于对格点计数）：

考虑点集 $S = { (x,y) in mathbb{Z}^2 mid 1 le x le frac{p1}{2}, 1 le y le frac{q1}{2} }$. 这个点集的数量是 $frac{p1}{2} frac{q1}{2}$。
我们考察直线 $y = frac{q}{p} x$（或者 $py = qx$）。这条直线穿过原点。
我们考虑位于这条直线两侧的点。

对于点 $(x,y) in S$，如果 $py < qx$，那么这个点在直线 $y = frac{q}{p}x$ 的上方。
如果 $py > qx$，那么这个点在直线 $y = frac{q}{p}x$ 的下方。
由于 $p, q$ 是素数，且 $x, y$ 的范围，点 $(x,y)$ 不可能在直线上。

我们将点集 $S$ 中的点按照它们是否在直线的上方或下方进行划分。
设 $N_+$ 是在直线上方（$py < qx$）的点数。
设 $N_$ 是在直线下方（$py > qx$）的点数。
总点数 $N = N_+ + N_ = frac{p1}{2} frac{q1}{2}$。

现在我们把 $left(frac{q}{p} ight)$ 和 $left(frac{p}{q} ight)$ 与 $N_+$ 或 $N_$ 联系起来。

考虑对于固定的 $x in {1, 2, dots, frac{p1}{2}}$, $y$ 的取值范围是多少使得 $py < qx$?
$y < frac{q}{p} x$.
所以 $y$ 的取值范围是 $1 le y < frac{q}{p} x$.
在整数范围内， $y$ 的取值个数是 $lfloor frac{q}{p} x floor$.
所以 $N_+ = sum_{x=1}^{frac{p1}{2}} lfloor frac{qx}{p} floor$.

类似地，考虑对于固定的 $y in {1, 2, dots, frac{q1}{2}}$, $x$ 的取值范围是多少使得 $qx > py$?
$x > frac{p}{q} y$.
所以 $x$ 的取值范围是 $frac{p}{q} y < x le frac{p1}{2}$.
在整数范围内，$x$ 的取值个数是 $frac{p1}{2} lceil frac{p}{q} y ceil + 1$.

这个计数方法需要更细致的分析来连接两个符号。

一个更经典的证明思路（基于高斯引理和二次互反律的特例）：

二次互反律可以分解为几个关键引理：
1. 引理 1: $left(frac{1}{p} ight) = (1)^{frac{p1}{2}}$。
证明：考虑 $x^2 equiv 1 pmod p$。根据欧拉判别法，$left(frac{1}{p} ight) equiv (1)^{frac{p1}{2}} pmod p$。由于 Legendre 符号只能是 $1$ 或 $1$，所以此式成立。
2. 引理 2: $left(frac{2}{p} ight) = (1)^{frac{p^21}{8}}$。
证明：利用高斯引理或更细致的计数方法，考虑集合 ${2, 4, 6, dots, (p1)}$. 对其模 $p$ 的剩余数进行分析。
3. 证明二次互反律的关键步骤： 假设 $p < q$ 是两个奇素数。我们想证明 $left(frac{p}{q} ight) = left(frac{q}{p} ight) (1)^{frac{p1}{2}frac{q1}{2}}$。
考虑由 $p$ 的所有二次剩余组成的集合 $R_p = {a in {1, dots, p1} mid left(frac{a}{p} ight) = 1}$.
考虑由 $q$ 的所有二次剩余组成的集合 $R_q = {b in {1, dots, q1} mid left(frac{b}{q} ight) = 1}$.

一个非常有启发性的证明来自 施瓦茨 (Schur)，它巧妙地利用了 域扩张 的思想，但对于初学者来说可能显得抽象。

我们回到 高斯引理 的版本，并尝试更直接地联系。
考虑高斯引理中，对 $left(frac{q}{p} ight)$ 的计算，我们考察集合 ${q, 2q, dots, frac{p1}{2}q}$ 模 $p$ 的剩余。
设 $kq = m_k p + r_k$, 其中 $0 le r_k < p$.
$left(frac{q}{p} ight) = (1)^N$，其中 $N$ 是 $r_k > p/2$ 的个数。

现在，我们将 $r_k$ 写成 $r_k = kq pmod p$。
如果 $r_k > p/2$，那么 $kq equiv r_k pmod p$ 并且 $r_k > p/2$.
如果 $r_k le p/2$, 那么 $kq equiv r_k pmod p$ 并且 $r_k le p/2$.

关键在于将 $q pmod p$ 的行为与 $p pmod q$ 的行为联系起来。
一个简洁证明往往会利用以下事实：
“如果 $q$ 是模 $p$ 的二次剩余，那么它会‘加速’这个过程。”

考虑模 $pq$ 的剩余环 $mathbb{Z}_{pq}$。
利用中国剩余定理 (CRT)， $mathbb{Z}_{pq} cong mathbb{Z}_p imes mathbb{Z}_q$.
二次剩余的性质在乘积环中也得以保持。

最简洁的证明之一可能涉及到 Dirichlet characters 的性质，但那会涉及更高级的数论工具。

让我们尝试一个相对“几何”的思路，仍然是基于计数。
考虑直线 $qx py = 0$ 穿过原点。
我们在第一象限考虑点 $(x, y)$，其中 $1 le x le frac{p1}{2}$ 和 $1 le y le frac{q1}{2}$。
这些点的数量是 $frac{p1}{2}frac{q1}{2}$。

我们对点 $(x,y)$ 根据 $qxpy$ 的符号进行分类。
$N_+ = \{(x,y) in S mid qx py > 0}$
$N_ = \{(x,y) in S mid qx py < 0}$
$N = N_+ + N_ = frac{p1}{2}frac{q1}{2}$

我们可以建立一个对应关系：
对于一个点 $(x, y) in S$, $qx py$ 的符号决定了它在 $y = frac{q}{p}x$ 的哪一侧。

这里的关键点是找到一个从 $S$ 到 $S'$ 的双射，其中 $S'$ 是由另一个对称性的计数得到的。

考虑一个与 $qxpy$ 相关的和。
我们想要 $left(frac{q}{p} ight)$ 和 $left(frac{p}{q} ight)$ 的关系。

假设 $p equiv 1 pmod 4$ 且 $q equiv 1 pmod 4$.
那么 $frac{p1}{2}$ 是偶数， $frac{q1}{2}$ 是偶数。$frac{(p1)}{2}frac{(q1)}{2}$ 是偶数。
二次互反律变为 $left(frac{p}{q} ight) = left(frac{q}{p} ight)$.

假设 $p equiv 3 pmod 4$ 且 $q equiv 1 pmod 4$.
那么 $frac{p1}{2}$ 是奇数， $frac{q1}{2}$ 是偶数。$frac{(p1)}{2}frac{(q1)}{2}$ 是偶数。
二次互反律变为 $left(frac{p}{q} ight) = left(frac{q}{p} ight)$.

假设 $p equiv 3 pmod 4$ 且 $q equiv 3 pmod 4$.
那么 $frac{p1}{2}$ 是奇数， $frac{q1}{2}$ 是奇数。$frac{(p1)}{2}frac{(q1)}{2}$ 是奇数。
二次互反律变为 $left(frac{p}{q} ight) = left(frac{q}{p} ight)$.

一个非常简洁且被广泛引用的证明思路是利用一个关于整数对 $(x, y)$ 的和：
考虑和 $S = sum_{k=1}^{frac{p1}{2}} leftlfloor frac{qk}{p} ight floor$.
根据高斯引理，$left(frac{q}{p} ight) = (1)^S$.

同时，我们也可以考虑形如 $sum_{k=1}^{frac{q1}{2}} leftlfloor frac{pk}{q} ight floor$.
这个和与 $left(frac{p}{q} ight)$ 有关。

欧拉提出的“飞镖”证明（几何解释）：
想象一个 $p imes q$ 的矩形，其角点在 $(0,0), (p,0), (0,q), (p,q)$。
考虑直线 $y = frac{q}{p} x$。
我们考虑满足 $1 le x le p1$ 和 $1 le y le q1$ 的整数点 $(x,y)$。
这些点都在直线 $y = frac{q}{p} x$ 的两侧。

关键在于将这些点按照是否能表示成 $qx'$ 或 $py'$ 的形式进行分类。
这个证明的实质在于分析 “被直线 $y=frac{q}{p}x$ 穿过的点” 的性质。

最简洁的证明，或许是基于一个恒等式。
Consider the sum $S = sum_{k=1}^{p1} left(frac{k}{p} ight)$. This sum is 0.
Consider the sum $T = sum_{k=1}^{p1} left(frac{k}{p} ight) k^{frac{q1}{2}}$.

让我们尝试一个基于 对称性 和 模运算 的证明。
考虑变量 $x in {1, 2, dots, p1}$。
我们考察 $x^{frac{q1}{2}} pmod q$ 的值。
由欧拉判别法，$left(frac{x}{q} ight) equiv x^{frac{q1}{2}} pmod q$.

现在我们看 $left(frac{p}{q} ight)$。
$left(frac{p}{q} ight) equiv p^{frac{q1}{2}} pmod q$.

设 $p$ 和 $q$ 是奇素数。
考虑集合 $S = {1, 2, dots, frac{p1}{2}}$.
我们考察 $q s pmod{p}$ 对于 $s in S$.
令 $q s equiv r_s pmod{p}$.
$left(frac{q}{p} ight) = (1)^{\{s in S mid r_s > p/2}}$.

一个被认为相对简洁且自洽的证明方法：
它建立在一个关于两个素数 $p, q$ 的恒等式上，该恒等式可以由 高斯二次域的理论 或 代数整数论 来证明，但我们可以尝试用初等方法来理解其核心。
核心思想是：对某个值 $n$ 进行计数，该计数可以通过两种不同的方式进行，最终得到一个关系式。

设 $n$ 是一个整数。考虑以下等式：
$$
sum_{k=1}^{p1} k^{frac{q1}{2}} equiv sum_{k=1}^{p1} left(frac{k}{q} ight) pmod q
$$
（这步的正确性需要验证，它并非直接的欧拉判别法应用）

实际上，一个更直接的证明涉及到对形如 $n^2 equiv a pmod{pq}$ 的方程解的研究。

最终，一个被认为是比较“优雅”且简洁的证明：

1. 我们知道欧拉判别法： $left(frac{a}{p} ight) equiv a^{frac{p1}{2}} pmod{p}$。
2. 因此，$left(frac{q}{p} ight) equiv q^{frac{p1}{2}} pmod{p}$。
3. 对调 $p, q$ 的角色， $left(frac{p}{q} ight) equiv p^{frac{q1}{2}} pmod{q}$。

现在的问题是如何联系 $q^{frac{p1}{2}}$ 和 $p^{frac{q1}{2}}$。
考虑表达式 $q^{frac{p1}{2}} pmod{pq}$。
由中国剩余定理，我们可以分别在模 $p$ 和模 $q$ 下考虑。

模 $p$: $q^{frac{p1}{2}} equiv left(frac{q}{p} ight) pmod{p}$。
模 $q$: $p^{frac{q1}{2}} equiv left(frac{p}{q} ight) pmod{q}$。

我们考虑一个特殊的代数结构，或者利用一些关于二次域的性质，可以证明：
$$
left(frac{p}{q} ight) = left(frac{q}{p} ight) (1)^{frac{(p1)}{2}frac{(q1)}{2}}
$$
这个结果，虽然证明过程可能需要一些技巧，但其形式本身就是简洁的。

简化证明的思路：
目标是证明 $left(frac{p}{q} ight) = left(frac{q}{p} ight)(1)^{frac{p1}{2}frac{q1}{2}}$。
这等价于证明 $left(frac{q}{p} ight) left(frac{p}{q} ight) = (1)^{frac{p1}{2}frac{q1}{2}}$。

使用高斯引理的一个版本：设 $p$ 为奇素数， $a$ 为不被 $p$ 整除的整数。令 $S = {a, 2a, dots, frac{p1}{2}a}$。令 $N$ 为 $S$ 中模 $p$ 后大于 $p/2$ 的数的个数。则 $left(frac{a}{p} ight) = (1)^N$。

我们对 $left(frac{q}{p} ight)$ 使用高斯引理，得到 $left(frac{q}{p} ight) = (1)^{N_q}$，其中 $N_q = \{k in {1, dots, frac{p1}{2}} mid qk pmod{p} > p/2 }$.
我们对 $left(frac{p}{q} ight)$ 使用高斯引理，得到 $left(frac{p}{q} ight) = (1)^{N_p}$，其中 $N_p = \{k in {1, dots, frac{q1}{2}} mid pk pmod{q} > q/2 }$.

我们需要证明 $N_q + N_p equiv frac{(p1)}{2}frac{(q1)}{2} pmod 2$。
这可以通过对 整数点计数 在 $y = frac{q}{p}x$ 直线两侧的数量进行巧妙的分析得到。
考虑点集 $S = { (x,y) in mathbb{Z}^2 mid 1 le x le frac{p1}{2}, 1 le y le frac{q1}{2} }$.
点 $(x,y)$ 在直线 $y = frac{q}{p}x$ 的上方意味着 $py < qx$.
点 $(x,y)$ 在直线 $y = frac{q}{p}x$ 的下方意味着 $py > qx$.

我们可以将 $N_q$ 的计数与 $sum_{x=1}^{frac{p1}{2}} lfloor frac{qx}{p} floor$ 联系起来。
以及将 $N_p$ 的计数与 $sum_{y=1}^{frac{q1}{2}} lfloor frac{py}{q} floor$ 联系起来。

关键证明步骤：
令 $N = \{ (x,y) mid 1 le x le frac{p1}{2}, 1 le y le frac{q1}{2}, py < qx }$.
令 $M = \{ (x,y) mid 1 le x le frac{p1}{2}, 1 le y le frac{q1}{2}, qx < py }$.
总数是 $frac{p1}{2}frac{q1}{2} = N+M$.

可以证明 $N = N_q$ （需要仔细论证）。
可以证明 $M = N_p$ （需要仔细论证）。

那么我们就需要证明 $N+M equiv frac{p1}{2}frac{q1}{2} pmod 2$.
这是因为我们证明了 $N equiv N_q pmod 2$ 和 $M equiv N_p pmod 2$.
所以 $N_q + N_p equiv N+M pmod 2$.
而 $N+M = frac{p1}{2}frac{q1}{2}$.
于是 $N_q + N_p equiv frac{p1}{2}frac{q1}{2} pmod 2$.
$left(frac{q}{p} ight) left(frac{p}{q} ight) = (1)^{N_q} (1)^{N_p} = (1)^{N_q+N_p} = (1)^{frac{p1}{2}frac{q1}{2}}$.

这就是二次互反律证明的核心思路。关键在于证明 $N = N_q$ 和 $M = N_p$，这需要仔细的计数和同余分析。

二次互反律的具体应用

二次互反律不仅仅是一个抽象的数论定理，它在数学和密码学领域有着至关重要的应用。

1. 简化 Legendre 符号的计算：
这是二次互反律最直接的应用。在计算 $left(frac{a}{p} ight)$ 时，如果 $a$ 很大，我们可以利用二次互反律将其转化为计算 $left(frac{p}{a} ight)$，或者更小的数对素数的 Legendre 符号的计算。通过不断地运用二次互反律以及 $1$ 和 $2$ 的符号性质，我们可以将复杂的 Legendre 符号计算简化到一个可以直接解决的形式。例如，计算 $left(frac{13}{23} ight)$：
$left(frac{13}{23} ight) = left(frac{23}{13} ight) (1)^{frac{12}{2}frac{22}{2}} = left(frac{23}{13} ight) (1)^{6 imes 11} = left(frac{23}{13} ight)$.
$left(frac{23}{13} ight) = left(frac{10}{13} ight) = left(frac{2 imes 5}{13} ight) = left(frac{2}{13} ight) left(frac{5}{13} ight)$.
$left(frac{2}{13} ight) = (1)^{frac{13^21}{8}} = (1)^{frac{168}{8}} = (1)^{21} = 1$.
$left(frac{5}{13} ight) = left(frac{13}{5} ight) (1)^{frac{4}{2}frac{12}{2}} = left(frac{13}{5} ight) (1)^{2 imes 6} = left(frac{13}{5} ight) = left(frac{3}{5} ight)$.
$left(frac{3}{5} ight) = left(frac{5}{3} ight) (1)^{frac{2}{2}frac{4}{2}} = left(frac{5}{3} ight) (1)^{1 imes 2} = left(frac{5}{3} ight) = left(frac{2}{3} ight)$.
$left(frac{2}{3} ight) = 1$.
所以，$left(frac{13}{23} ight) = (1) imes (1) = 1$.
这展示了如何通过一系列的互反律变换来计算 Legendre 符号。

2. 解决二次同余方程：
二次互反律是判断方程 $x^2 equiv a pmod{p}$ 是否有解的关键工具。如果 $left(frac{a}{p} ight) = 1$，则方程有解；如果 $left(frac{a}{p} ight) = 1$，则无解。这在理论研究和实际问题中都有应用，例如在构造某些类型的数学结构时。

3. 在密码学中的应用：
二次互反律是许多现代密码学算法的基础，尤其是基于数论假设的公钥密码系统。
GoldwasserMicali (GM) 公钥密码体制： 这是最早的基于二次剩余问题的公钥密码体制之一。GM 体制利用了判断一个大数是否为二次剩余的困难性。在加密过程中，需要计算一个随机数 $r$ 的二次剩余性模一个大素数 $p$，这依赖于对二次互反律的理解。当发送方发送一个比特 $b=0$ 时，发送 $r^2 pmod p$（一个二次剩余）；当发送 $b=1$ 时，发送 $a cdot r^2 pmod p$（其中 $a$ 是一个二次非剩余）。接收方通过计算 $left(frac{a}{p} ight)$ 来判断接收到的数是二次剩余还是二次非剩余，从而恢复比特。
SolomonGoldwasser 公钥密码体制： 这是 GM 体制的一个变体，其安全性也依赖于二次剩余的困难性。
ElGamal 密码体制的变种： 虽然 ElGamal 主要基于离散对数问题，但在一些变种或改进中，也会涉及到二次剩余的性质。
安全多方计算和零知识证明： 在构建安全多方计算协议和零知识证明系统中，常常需要利用二次剩余的性质来验证某些计算的正确性或保密性。例如，可以设计协议来证明一个人知道一个数的平方根，而无需透露该数本身。

4. 在计算数学和代数数论中的应用：
二次互反律是数论中一个贯穿始终的定理。它在代数数论中，特别是在二次域的研究中，扮演着核心角色。二次域的类数、单位群等重要性质都与其密切相关。例如，二次互反律的推广——Artin 猜想 和 Dirichlet $L$函数 的性质，都建立在二次互反律的逻辑和数学思想之上。

总结来说，二次互反律以其优美的形式和深刻的内涵，连接了素数的二次剩余性质。它的简洁证明体现了数学家的智慧，而它在计算、密码学和代数数论中的广泛应用，则证明了其作为数论基石的不可替代的价值。

这里有个我觉得挺简洁但又很神奇的证明，用到的工具只有排列的逆序数。发现者是 19 世纪的俄国数学家 Zolotarev. 可以简要说说。

如果有 个字母的一个排列 ，它总可以写成一串对换的乘积，写法有很多，但用到的对换的个数的奇偶性是不变的，所以可以定义 的符号 ，用到偶数个对换的时候符号是 1，用到奇数个对换的时候符号是 -1.

符号是一个同态：如果有两个排列 , 则

他们乘积的符号等于符号的乘积：

证明的思路很神奇，找两个排列 使得他们的符号分别是 , 然后乘积的符号是 ，就成了。

---

对于两个奇素数 , 取 个字母，填入 的方格内。

比如 的情形，可以按从左到右从上到下的顺序填入 0-9a-e 十五个字母。

       0 1 2 3 4 5 6 7 8 9 a b c d e     

沿着对角线捡起来，再横着填到填入一个 的方格，则得到了 0-9a-e 的一个排列 .

       0 1 2 3 4            0 6 c 3 9 5 6 7 8 9 -------->  a 1 7 d 4 a b c d e            5 b 2 8 e     

这里的对角线是贪食蛇模式，如果碰到了底部就从上面继续，碰到了右边就从左边继续。这个排列的意思就是 0 -> 0, 1 -> 6, 2 -> c, 3 -> 3, 4 -> 9, ...

现在把这 的方格的内容横着捡起来（0 6 c 3 9 a 1 7 d 4 5 b 2 8 e），按从左到右从上到下的顺序填入一个 的方格

                               0 6 c 0 6 c 3 9               3 9 a a 1 7 d 4 ----------->  1 7 d 5 b 2 8 e               4 5 b                         2 8 e     

这一步没有重排字母（恒同映射），只是为下一步做个准备。

现在在 的方格里横着捡起来，沿对角线填入

       0 6 c              0 5 a 3 9 a              1 6 b 1 7 d -----------> 2 7 c 4 5 b              3 8 d 2 8 e              4 9 e     

这是另一个排列 . 这次排列以后的结果很有意思，0 1 2 3 4 变成竖着写的了：所以 的复合，相当于 “转置” 了原来的方格（在 3 x 5 的方格里沿对角线捡起来，横着放下去，再横着捡起来，沿着对角线放到 5 x 3 的方格里去，中间两项一抵消，剩下的当然就是转置）

                                                      0 6 c              0 5 a 0 1 2 3 4      σ        0 6 c 3 9     id       3 9 a      τ       1 6 b 5 6 7 8 9 ----------->  a 1 7 d 4 -----------> 1 7 d -----------> 2 7 c a b c d e               5 b 2 8 e              4 5 b              3 8 d                                                2 8 e              4 9 e     

注意转置不是平凡的排列，是把 01234... 分别变成 05a16...

---

下面来计算这几个排列的符号。

转置的比较好算：要把

       0 5 a 1 6 b 2 7 c 3 8 d 4 9 e     

“恢复” 成 0123456789abcde 需要几个对换？计算“恢复”每个字母位置对符号带来的贡献就行——要把 1 放到 0 的后面，需要越过 5 和 a, 两个对换，因为我们只关心奇偶性，所以无贡献。要把 2 放到 1 的后面，需要越过 5, a, 6, b, 总共 4 个对换，也无贡献。可以看出 0 1 2 3 4 归位都是无贡献的。5 也没有，6 就比较有趣了，只需要越过 a, 贡献了一个 -1. 7 呢？7 每往上移动一行贡献一个 -1, 但是需要往上移动两行，所以 无贡献。8 贡献了 ，9 贡献了 ...

一般地如果写成 的方格，

       xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xoxoxoxoxoxoxoxoxoxoxoxoxoxoxox xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xoxoxoxoxoxoxoxoxoxoxoxoxoxoxox xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xoxoxoxoxoxoxoxoxoxoxoxoxoxoxox xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx     

只有标 "o" 的地方能给出 -1 的因子（每个 o 需要越过奇数个字母奇数次），所以转置的符号是. 这里就有点二次互反律的影子了。

那么

       0 1 2 3 4     σ       0 6 c 3 9 5 6 7 8 9 --------->  a 1 7 d 4 a b c d e             5 b 2 8 e     

的符号怎么计算呢？计算这个才是写成 方格的原因——沿着对角线重写的时候，可以观察到，每个字母所在的列都没有变化，只是行变了，所以 其实是五个置换的乘积（每个对应一列），而且我们可以通过 “旋转密码锁” 的方式（每次旋转不改变符号），看出 和下面这个置换有相同的符号

       0 1 2 3 4     σ'      0 1 2 3 4 5 6 7 8 9 --------->  a b c d e a b c d e             5 6 7 8 9     

而这个东西的符号，其实就是第一列那个置换的符号的五次方——等于第一列那个置换的符号。

而第一列那个置换，可以证明，就是 “乘以5” 在 上定义的置换。也就是说， 的符号就是 “乘以5” 在 上的置换的符号。

同理， 的符号就是 “乘以3” 在 上的置换的符号。

一般地对于 , 把 “乘以 m” 在 上的置换的符号，记作 的话，我们已经证明了

接下来只需说明 ，而这并不难—— 是素数的时候 都是 到 的满同态（不是完全显然的，想想为什么是同态，为什么满），而这样的同态只有一个，所以他们一定相等。这就赢了。

---

我不知道这个证明是怎么想出来的，但是证明本身似乎比数格点之类的证明好懂一点，也难忘一点。把一个群 ({±1}) 里的一个等式（用同态）提升到某个复杂点（所以更有信息量）的群 (S_n) 里证明出来，很好用，也很需要创造力。

来一个我大Eisenstein的解析证明。这个证明据说是Kummer给予高度评价的证明。下面证明来自Franz Lemmermeyer的书Reciprocity Laws(From Euler to Eisenstein), pp. 236-237.

证明： 设p,q均为奇质数。首先证明以下等式是成立的。定义

那么有

。

首先如果 ,那么必存在 ,使得 。正负号由r惟一决定。当r走遍A中所有元素，那么r'也走遍A中元素，且没有重复。上面的同余式总意味着

令r取遍A中所有值，并且结合Euler引理 ,命题得证。

Eisenstein 接着利用正弦函数的性质(容易用归纳法证明)

引理：对奇数 ， 是 的多项式。记 ,那么这个多项式 是 的多项式，而且多项式是首项系数为 的偶函数。

的零点是 的零点除去 的整数倍。我们如果定义r与-r是等价的，那么在此等价关系下q的剩余系(不含0)的代表元的集合可以定义为 。我们有

。

回到Legendre符号的乘积表达式。我们立刻有

交换p与q, 二重乘积正好改变

次符号。证毕。[天才的证明!!!