オイラーの規準

$(\mathbb{Z}/p\mathbb{Z})^{*}$ は位数 $p-1$ の巡回群である(素数を法とする標準的な事実)ので、原始根 $g$ を一つ固定し $a \equiv g^k \pmod p$($0 \le k \le p-2$)と書く。$p$ を法とする平方剰余はちょうど $g$ の偶数乗である:$a=g^{2m}$ なら $x=g^m$ が $x^2\equiv a$ を満たし、逆にすべての平方 $x^2=(g^j)^2=g^{2j}$ は偶数乗である。したがって $a$ が平方剰余であることは $k$ が偶数であることと同値である。

次に $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$ を計算する。$k$ が偶数のとき $k=2m$ と書けば、フェルマーの小定理より $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$ となり、剰余の場合と一致する。

$k$ が奇数のとき、$g^{k(p-1)/2}$ は $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$ の平方根なので $a^{(p-1)/2}\equiv \pm 1$ である。これが $1$ になることはない:もしそうなら $g$ の位数が $k(p-1)/2$ を割り切る必要があるが、$\operatorname{ord}(g)=p-1$ であり $k$ が奇数だと $(p-1)/2$ 自体が倍数でない限り $k(p-1)/2$ は $p-1$ の倍数にならず、$g$ が正確に位数 $p-1$ の原始根であることに矛盾する。よって $k$ が奇数のときちょうど $a^{(p-1)/2}\equiv -1\pmod p$、すなわち $a$ が非剰余のときちょうどこれが成り立つ。

両方の場合をまとめると:$a^{(p-1)/2}\equiv 1\pmod p$ であることは $a$ が平方剰余であることと同値であり、そうでなければ $\equiv -1$ となる。これはまさに $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$ の主張である。