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

証明.$x^2-y^2=(x-y)(x+y)$である。§A4.2 補題 2.1により、$p\mid(x-y)(x+y)$ならば$p\mid x-y$または$p\mid x+y$である。逆に、いずれかの因子が$p$で割り切れれば、その積も$p$で割り切れる。▨

証明.$1\le x\le p-1$とする。補題 1.3により、$1,\ldots,p-1$のうち、平方が$x^2$と法$p$で合同である数は$x$と$p-x$だけである。$p$は奇数なので$x\ne p-x$である。したがって$1,\ldots,p-1$は、平方が同じ剰余をもつ二つの数の組に分かれる。各組に一つの平方剰余が対応し、異なる組には異なる平方剰余が対応するので、平方剰余の個数は$(p-1)/2$である。▨

証明.§A4.12 定理 3.2により、法$p$の原始根$g$を取る。$g$の位数は$p-1$であり、§A4.12 系 2.2により、$g^0,g^1,\ldots,g^{p-2}$は法$p$で相異なる非零の剰余類を表す。したがって$a\equiv g^k\pmod p$を満たす整数$k$が$0\le k\le p-2$の範囲にただ一つ存在する。

$k=2j$なら$a\equiv(g^j)^2\pmod p$であり、$a$は平方剰余である。逆に$a\equiv x^2\pmod p$とする。$p\nmid x$なので$x\equiv g^t\pmod p$を満たす整数$t$を$0\le t\le p-2$の範囲に取ることができる。$g^k\equiv g^{2t}\pmod p$である。$k\ne2t$の場合は、§A4.5 命題 3.2により$g^{|k-2t|}\equiv1\pmod p$であり、§A4.12 命題 1.2により$p-1\mid|k-2t|$である。$k=2t$の場合も含めて、$k\equiv2t\pmod{p-1}$である。$p-1$は偶数なので$k$は偶数である。よって$a$が平方剰余であることと$k$が偶数であることは同値である。

$h=(p-1)/2$とおく。$(g^h)^2\equiv1\pmod p$であるから、補題 1.3により$g^h\equiv1\pmod p$または$g^h\equiv-1\pmod p$である。$0<h<p-1$と$g$の位数が$p-1$であることから$g^h\not\equiv1\pmod p$なので、$g^h\equiv-1\pmod p$である。したがって

が成り立つ。▨

証明. オイラーの規準を$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.3の証明と同じ理由で合同は等号に強まる。▨