離散フーリエ変換による平方剰余の相互法則の証明

$\mathbb{F}_p$は体なので, $0$以外の元は可逆である. したがって, $\mathbb{F}_p^{\times}$の位数は$p-1$である.

$x$を$\mathbb{F}_p^{\times}$の位数最大の元とし, その位数を$d$とする. $d = p-1$であることを示す.

まず, $\mathbb{F}_p^\times$のすべての元は位数が$d$の約数である. もし, 位数が$d$の約数でない元$y$が存在したとし, その位数を$c$する. このとき, $xy$の位数は$d$と$c$の最小公倍数となり, $d$より大きくなるが, これは$d$の定義に矛盾する.

よって, $\mathbb{F}_p^\times$の元は全て方程式$X^d = 1$を満たす. しかし, $\mathbb{F}_p^\times$は整域なので, その上の$d$次方程式は$d$個以下の解しか持たない. よって, $d = p-1$. $\square$

まず, フェルマーの小定理より, $\mathbb{F}_p^\times$の任意の元$x$は$x^{p-1} = 1$であり, $X^2 = 1$を満たす$\mathbb{F}_p^\times$の元は$\pm 1$だけなので, $a^{\frac{p-1}{2}} = \pm 1$である.

$\mathbb{F}_p^\times$の生成元を$x$とする. もし, $a$が平方剰余なら, ある$m$が存在して, $a = x^{2m}$となっている. よって,
$$ a^{\frac{p-1}{2}} = (x^{p-1})^m = 1. $$
逆に, $a^{\frac{p-1}{2}} = 1$とする. $a = x^n$ $(0 \le n \le p -1)$とおくと, $a^{\frac{p-1}{2}} = x^{\frac{p-1}{2}n} = 1$で, $x$の位数は$p-1$なので, $\frac{p-1}{2}n$は$p-1$の倍数である. よって$n$は偶数. $\square$

$f \mapsto \hat{f}$は, $\mathbb{C}$ベクトル空間$L^2(\mathbb{F}_p) := \{ f: \mathbb{F}_p \to \mathbb{C} \}$の線形写像なので, 基底に対して示せば十分である.
$L^2(\mathbb{F}_p)$の基底として, 各$a \in \mathbb{F}_p$に対して,
$\begin{eqnarray} \delta_a(x) := \left\{ \begin{array}{l} 1 \ \ (x = a) \\ 0 \ \ (x \neq a) \end{array} \right. \end{eqnarray}$
を取る.

$\begin{eqnarray} \hat{\hat{\delta_a}}(z) &=& \sum_{y = 0}^{p - 1} \hat{\delta_a}(y) \exp(\frac{-2 \pi i yz}{p}) \\ &=& \sum_{y = 0}^{p - 1} \sum_{x = 0}^{p - 1} \delta_a(x) \exp(\frac{-2 \pi i xy}{p}) \exp(\frac{-2 \pi i yz}{p}) \\ &=& \sum_{x = 0}^{p - 1} \delta_a(x) \sum_{y = 0}^{p - 1} \exp(\frac{-2 \pi i xy}{p}) \exp(\frac{-2 \pi i yz}{p}) \\ &=& \sum_{x = 0}^{p - 1} \delta_a(x) \sum_{y = 0}^{p - 1} \exp(\frac{-2 \pi i (x + z)y}{p}) \\ &=& \sum_{y = 0}^{p - 1} \exp(\frac{-2 \pi i (a + z)y}{p}) \end{eqnarray}$

$z = -a$のとき,
$$ \sum_{y = 0}^{p - 1} \exp(\frac{-2 \pi i (a + z)y}{p}) = p = p \delta_a(-z). $$

$z \neq -a$のとき,
$$ \sum_{y = 0}^{p - 1} \exp(\frac{-2 \pi i (a + z)y}{p}) = 0 = p \delta_a(-z). \square $$

補題6より,
$$ (\frac{p^*}{q}) g_p \equiv g_p^q \mod q $$
環$\mathbb{Z}[\exp(\frac{2 \pi i}{p})]$で$\mod q$で考えれば,

$\begin{eqnarray} g_p^q &=& \hat{h_p}(-1)^q \equiv \sum_{x = 0}^{p-1} (\frac{x}{p})\exp(\frac{2 \pi i x q}{p}) \mod q \\ &\equiv& \sum_{z = 0}^{p-1} (\frac{z q^{-1}}{p})\exp(\frac{2 \pi i z}{p}) \mod q \\ &\equiv& (\frac{q}{p})\sum_{z = 0}^{p-1} (\frac{z}{p})\exp(\frac{2 \pi i z}{p}) \mod q \\ &\equiv& (\frac{q}{p}) g_p \mod q. \end{eqnarray}$

両辺に$g_p$をかけると, 補題5より,
$$ (\frac{p^*}{q})p^* \equiv (\frac{q}{p}) p* \mod q. $$
$p^*$は$q$と互いに素な整数なので, $\mod q$で可逆. よって,
$$ (\frac{p^*}{q}) \equiv (\frac{q}{p}) \mod q. $$
両辺は$\pm 1$しか取らないので,
$$ (\frac{p^*}{q}) = (\frac{q}{p}). \square $$

$y \neq 0$のとき,
$\begin{eqnarray} \hat{h_p}(-y) &=& \sum_{x = 0}^{p - 1} (\frac{x}{p}) \exp(\frac{2 \pi i xy}{2}) \\ &=& \sum_{z = 0}^{p-1} (\frac{z y^{-1}}{p}) \exp(\frac{2 \pi i z}{p}) \\ &=& (\frac{y}{p})\sum_{z = 0}^{p-1} (\frac{z}{p}) \exp(\frac{2 \pi i z}{p}) \\ &=& h_p(y) g_p. \end{eqnarray}$

$y = 0$のとき, $\displaystyle \hat{h_p}(-y) = \sum_{x = 0}^{p -1} (\frac{x}{p}) = 0. $ $\square$

上の補題の両辺をフーリエ変換して,
$$ \hat{\hat{h_p}}(-x) = \hat{h_p}(x) g_p. $$
反転公式より,
$$ \hat{\hat{h_p}}(-x) = ph_p(x) $$
両式の右辺に$x = -1$を代入すると,
$$ g_p^2 = p^*. \square $$

補題5より,
$\begin{eqnarray} (\frac{p^*}{q}) &\equiv& (\frac{g_p^2}{q}) \mod q \\ &\equiv& (g_p^2)^{\frac{q-1}{2}} \mod q \\ &\equiv& g_p^{q-1} \mod q . \ \square \end{eqnarray}$