オイラーの基準
定理 1
素数について $p \ne 2$ $$ a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p} $$
説明
これによると、$a$ が二次剰余か非二次剰余かを見たい場合は、ただ計算すればいい。もちろん累乗はそう簡単な作業ではないが、全数を計算するよりはマシだろう。証明自体はそれほど難しくはないが、補助定理が多く用いられるため、ある程度の勉強が必要だ。
証明
$a$ がQRの場合とNRの場合に分けて考えよう。
Case 1. $a$がQRの場合
$a$がQRであるため、ある$b$に対して $a = b^2$ が成り立ち、次のようになる。 $$ a^{p-1 \over 2} \equiv b^2{p-1 \over 2} \equiv b^{p-1} \pmod{p} $$
フェルマーの小定理: $a^{p-1} \equiv 1 \pmod{p}$
フェルマーの小定理により $b^{p-1} \equiv 1 \pmod{p}$ となるので $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv 1 \pmod{p} $$
Case 2. $a$がNRの場合
合同方程式 $x^{p-1} - 1 \equiv 0 \pmod{p}$ から始める。
合同方程式の代数学の基本定理: $f(x)=a_{ 0 }x^{ d }+a_{ 1 }x^{ d-1 }+ \cdots +a_{ d-1 }x+a_{ d }$ に対して方程式 $f(x)\equiv 0 \pmod{p}$ は、多くても $d$ 個の合同でない解を持つ
代数学の基本定理により、以下の合同方程式は $p-1$ 個の合同でない解を持つ。
$$ 0 \equiv x^{p-1} - 1 \equiv (x^{p-1 \over 2} +1) (x^{p-1 \over 2} -1) \pmod{p} $$
QRとNRの個数: $2$ より大きい素数 $p$ について、QRとNRは正確に $\displaystyle {(p-1) \over 2}$ 個存在する
一方で、素数 $p$ についてQRとNRは正確に $\displaystyle {p-1 \over 2}$ 個ずつ存在し、Case 1で見たように、$\displaystyle {p-1 \over 2}$ 個のQRは$\displaystyle (x^{p-1 \over 2} -1) \equiv 0 \pmod{p}$ の解である。つまり、残りの $\displaystyle {p-1 \over 2}$ NRは $(x^{p-1 \over 2} +1) \equiv 0 \pmod{p}$ の解でなければならない。したがって、次のようになる。 $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv -1 \pmod{p} $$
Case 1, 2を統合すると、次のように得られる。 $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \pmod{p} $$
■
Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p150. ↩︎