📂整数論

オイラーの判定法

定理¹

素数 $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} $$

■