📂整数論

オイラーの基準

定理 ¹

素数について $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}$$

■