オイラーの規準

この証明は素数を法とする剰余のクラスが体であることを使用する。詳細は素体の記事(en:Characteristic (algebra)#Case of fields)参照。

法が素数であるため、ラグランジュの定理（英語版）が適用される。次数 k の多項式は最大で k 個の根しか持つことができない。特に、x² ≡ a (mod p) は各 a に対して最大2つの解を持つ。このことは0の他にpを法とする少なくともp − 1/2個の異なる平方剰余があることを即座に意味する。x の p − 1 個の可能な値の各々は、同じ剰余を与えるために互いに付随することしかできない。

実際に、${\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}}$である。これは${\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}}$であるからである。 よって、${\displaystyle {\tfrac {p-1}{2}}}$ 個の別個の平方剰余は ${\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}}$である。

a は p と互いに素であるため、フェルマーの小定理により

${\displaystyle a^{p-1}\equiv 1{\pmod {p}},}$

となり、これは

${\displaystyle \left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.}$

と書くことができる。 p を法とする整数は体を形成するため、それぞれの a についてこれらの因数のいずれかがゼロでなければならない。

ここで a が平方剰余 a ≡ x² であるとすると

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.}$

となる。よって平方剰余 (mod p) により第1の因数がゼロになる。

ラグランジュの定理を再度適用すると、第1の因数をゼロにするaの値は p − 1/2 より多くはないことに留意する。しかし、最初に述べたように少なくとも p − 1/2 個の異なる平方剰余 (mod p) がある（0以外）。よって、これらはきっかりと第1の因数をゼロにする剰余クラスである。もう1つの p − 1/2 個の剰余クラス（非剰余）は2番目の因数がゼロである必要があり、そうでないとフェルマーの小定理を満たさない。これがオイラーの規準である。

例 1: aが平方剰余になる奇素数pを見つける

a=3が平方剰余となる奇素数pを小さい方から求めてみる。

剰余が3であるから、pは4以上である。 また、pは素数なので5以上(5, 7, 11, ...)のみを判定すればよい。

ここでオイラーの規準を用いると、

p = 5を判定してみる。 3^{(5 − 1)/2} = 3² ≡ 9 ≡ -1 (mod 5)となり、3は5を法とする平方剰余ではない。

p = 7を判定してみる。 3^{(7 − 1)/2} = 3³ ≡ 27 ≡ -1 (mod 7)となり、3は7を法とする平方剰余ではない。

p = 11を判定してみる。 3^{(11 − 1)/2} = 3⁵ ≡ 243 ≡ +1 (mod 11)となり、3は11を法とする平方剰余である。

p = 13を判定してみる。 3^{(13 − 1)/2} = 3⁶ ≡ 729 ≡ +1 (mod 13)となり、3は13を法とする平方剰余である。

p = 17を判定してみる。 3^{(17 − 1)/2} = 3⁸ ≡ 6561 ≡ -1 (mod 17)となり、3は17を法とする平方剰余ではない。

値を計算し続けると、次の結果となる(括弧はルジャンドル記号)。

(3/p) = +1 となるのは p = {11, 13, 23, 37, ...}の場合である。つまり3はこれらのpを法とした平方剰余である。

(3/p) = −1 となるのは p = {5, 7, 17, 19, 29, 31, ...}の場合である。つまり3はこれらのpを法とした平方剰余ではない。

例 2: 与えられた奇素数pを法とする平方剰余を見つける

奇素数p=17を法とする平方剰余はどの数であるか？

まずオイラーの規準を用いずに実際に計算してみると下記のようになる。

1² = 1 ≡ 1 (mod 17)

2² = 4 ≡ 4 (mod 17)

3² = 9 ≡ 9 (mod 17)

4² = 16 ≡ 16 (mod 17)

5² = 25 ≡ 8 (mod 17)

6² = 36 ≡ 2 (mod 17)

7² = 49 ≡ 15 (mod 17)

8² = 64 ≡ 13 (mod 17).

残りの9から16までは、既に求めた8から1までと対称的に同じ値となるため、わざわざ求める必要はない。

(たとえば 11 ≡ −6 (mod 17) であるから、11² ≡ (−6)² ≡ 6² ≡ 2 (mod 17))。

よって、17を法とする平方剰余のセットは {1, 2, 4, 8, 9, 13, 15, 16} と求められる。

これをオイラーの規準を使用することで求めてみる。

1^{(17 − 1)/2} = 1⁸ ≡ 1 ≡ +1 (mod 17) であるため、1は17を法とする平方剰余である。

2^{(17 − 1)/2} = 2⁸ ≡ 256 ≡ +1 (mod 17) であるため、2は17を法とする平方剰余である。

3^{(17 − 1)/2} = 3⁸ ≡ 6561 ≡ −1 (mod 17) であるため、3は17を法とする平方剰余ではない。

4^{(17 − 1)/2} = 4⁸ ≡ 65536 ≡ +1 (mod 17) であるため、4は17を法とする平方剰余である。

5^{(17 − 1)/2} = 5⁸ ≡ 390625 ≡ −1 (mod 17) であるため、5は17を法とする平方剰余ではない。

これを16まで続けると、前述と同様に {1, 2, 4, 8, 9, 13, 15, 16} が平方剰余となる。

オイラーの規準は平方剰余の相互法則と関連する。

実際には、ユークリッドの互除法の拡張した変形を使用してヤコビ記号 ${\displaystyle \left({\frac {a}{n}}\right)}$ を計算する方が効率的である。${\displaystyle n}$ が奇素数である場合、これはルジャンドル記号と等しく、 ${\displaystyle a}$ が ${\displaystyle n}$ を法とする平方剰余であるかどうかを決定する。

一方で、ヤコビ記号と${\displaystyle a^{\frac {n-1}{2}}}$の同等性は全ての奇素数に当てはまるが、必ずしも合成数には当てはまらないため、両方を計算してそれらを比較することで素数判定、特にソロベイ–シュトラッセン素数判定法として使用することができる。所与の${\displaystyle a}$に対して合同が成り立つ合成数は、底 ${\displaystyle a}$ に対するオイラー・ヤコビ擬素数(en:Euler–Jacobi pseudoprime)と呼ばれる。