平方剰余とオイラーの規準

$p$ を奇素数、$p\nmid a$ とし、$b=a^{\frac{p-1}{2}}$ とおきます。フェルマーの小定理より $b^2=a^{p-1}\equiv 1(\mathrm{mod}p)$ なので、$p\mid (b-1)(b+1)$ です。$p$ は素数なので $p\mid b-1$ または $p\mid b+1$、つまり $b\equiv 1$ または $b\equiv -1(\mathrm{mod}p)$ です。さらに $p\ge 3$ なので $1\not\equiv -1(\mathrm{mod}p)$ であり、この 2 つの場合ははっきり分かれます。

まず $a$ が平方剰余で $a\equiv x^2$ のときを考えます。$p\nmid x$ なので、$b\equiv x^{p-1}\equiv 1$ です。次に平方剰余の個数を数えます。$1\le x,y\le p-1$ のとき、$x^2\equiv y^2$ は $p\mid (x-y)(x+y)$、すなわち $x\equiv \pm y$ と同じ条件です。したがって $1^2,2^2,\dots ,(p-1{)}^2$ の余りはちょうど $\frac{p-1}{2}$ 種類で、平方剰余はちょうど $\frac{p-1}{2}$ 個あります。ここで次の事実を使います。「$p$ が素数で、$f(X)$ が最高次の係数 $1$ の $d$ 次の整数係数多項式（$d\ge 1$）なら、$f(s)\equiv 0(\mathrm{mod}p)$ を満たす整数 $s$ は法 $p$ で高々 $d$ 個」です。最高次の係数が $1$ なので、$f$ は法 $p$ で $0$ の多項式ではありません。これを $d$ に関する帰納法で示します。$d=1$ なら $f(X)=X+c$ で、解は $s\equiv -c$ の 1 個だけです。$d\ge 2$ のとき、解が 1 つもなければ明らかなので、解 $r$ があるとします。$f(X)$ を $X-r$ で割ると $f(X)=(X-r)g(X)+f(r)$ となり、$g(X)$ は最高次の係数 $1$ の $d-1$ 次の整数係数多項式です（割る式の最高次の係数が $1$ なので、割り算は整数係数のままできます）。$f(r)\equiv 0$ なので、どの整数 $s$ を代入しても $f(s)\equiv (s-r)g(s)(\mathrm{mod}p)$ です。$s\not\equiv r$ である別の解 $s$ をとると、整数として $(s-r)g(s)\equiv 0(\mathrm{mod}p)$ です。$p$ は素数で $p\nmid s-r$ なので、$p\mid g(s)$ となり、$s$ は $g(X)\equiv 0$ の解です。帰納法の仮定より、$g(X)\equiv 0$ の解は高々 $d-1$ 個です。よって $f(X)\equiv 0$ の解は $r$ と合わせて高々 $d$ 個です。この事実を最高次の係数 $1$ の多項式 $X^{\frac{p-1}{2}}-1$ に当てはめると、$X^{\frac{p-1}{2}}\equiv 1$ の解は高々 $\frac{p-1}{2}$ 個です。その枠は $\frac{p-1}{2}$ 個の平方剰余ですでに埋まっています。ゆえに平方非剰余 $a$ では $b\not\equiv 1$、つまり $b\equiv -1$ です。以上より、オイラーの規準 $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$ が成り立ちます。$p\mid a$ のときも両辺とも $0$ と合同なので、この式は成り立ちます。

乗法性は指数法則から導けます。$(ab{)}^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}{b}^{\frac{p-1}{2}}$ なので、$\left(\frac{ab}{p}\right)\equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)(\mathrm{mod}p)$ です。両辺はどちらも $1,-1,0$ のいずれかなので、差の絶対値は高々 $2$ です。$p\ge 3$ なので、合同であれば等号 $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ が成り立ちます。特に、平方非剰余どうしの積は平方剰余になります。