§A4.13平方剰余とルジャンドル記号

証明. 写像$\phi : \{1, \dots, p-1\} \to \{1, \dots, p-1\}$，$\phi(x) = x^2 \bmod p$を考える。まず$x^2 \equiv y^2 \pmod p$と$x \equiv \pm y \pmod p$が同値であることを見る：

これは$p$が素数であることから従う（ユークリッドの補題、基礎）。$1 \le x \le p-1$の範囲で$x \equiv -x \pmod p$となるのは$p \mid 2x$すなわち$p \mid x$の場合だけだが、$1 \le x \le p-1$ではこれは起こらない。したがって$x \ne -x \pmod p$が常に成り立ち、$\{x, p-x\}$の各ペアはちょうど同じ平方の値を与える相異なる2元の組になる。$1, \dots, p-1$は$\frac{p-1}{2}$組のこのようなペアに分割されるので、$\phi$の像（＝平方剰余の集合）はちょうど$\dfrac{p-1}{2}$個の相異なる値からなる。▨

証明. 法$p$の原始根$g$を1つとる（§A4.12 定理 2.1）。$g$の位数は$p - 1$なので、$a = g^k$（$0 \le k \le p-2$）とただ一通りに書ける。

$a$が平方剰余$\iff$$k$が偶数：$k = 2j$なら$a = (g^j)^2$は平方剰余。逆に$a = x^2$とし$x = g^t$と書けば$a = g^{2t}$となり、$g^k = g^{2t}$から$k \equiv 2t \pmod{p-1}$。$p - 1$は偶数なので、$2t$に$p-1$の倍数を足しても偶奇は変わらず、$k$は偶数。

$g^{\frac{p-1}{2}} \equiv -1 \pmod p$であること：$\bigl(g^{\frac{p-1}{2}}\bigr)^2 = g^{p-1} \equiv 1 \pmod p$なので$g^{\frac{p-1}{2}}$は$x^2 \equiv 1 \pmod p$の解、すなわち$\pm 1$（$x^2 - 1 = (x-1)(x+1)$と$p$が素数であることから、解は$1, -1$の 2つのみ）。もし$g^{\frac{p-1}{2}} \equiv 1$なら$g$の位数が$p-1$より小さい$\frac{p-1}{2}$以下になり、$g$が原始根であることに矛盾する。よって$g^{\frac{p-1}{2}} \equiv -1 \pmod p$。

結論：$a^{\frac{p-1}{2}} = g^{k \cdot \frac{p-1}{2}} = \bigl(g^{\frac{p-1}{2}}\bigr)^k \equiv (-1)^k \pmod p$。$k$が偶数（$a$が QR）なら$(-1)^k = 1$、$k$が奇数（$a$が QNR）なら$(-1)^k = -1$。これはまさに$\left(\frac{a}{p}\right)$の値と一致する。▨

証明. オイラーの規準を$a = -1$に適用すれば$\left(\frac{-1}{p}\right) \equiv (-1)^{\frac{p-1}{2}} \pmod p$。両辺とも$\{-1, 1\}$に値を持ち、$p \ge 3$なので$-1 \not\equiv 1 \pmod p$。よって mod$p$での合同は整数としての等号を意味する。$\dfrac{p-1}{2}$が偶数（$p \equiv 1 \pmod 4$）なら値は$1$、奇数（$p \equiv 3 \pmod 4$）なら$-1$。▨

証明. オイラーの規準より

両辺は$\{-1, 1\}$に値を持ち$p \ge 3$なので、系 2.2の証明と同じ理由で合同は等号に強まる。▨