オイラーの規準
a p − 1 ≡ 1 ( mod p ) , {\displaystyle a^{p-1}\equiv 1{\pmod {p}},}
となり、これは
( a p − 1 2 − 1 ) ( a p − 1 2 + 1 ) ≡ 0 ( mod 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 であるとすると
a p − 1 2 ≡ ( x 2 ) p − 1 2 ≡ x p − 1 ≡ 1 ( mod p ) . {\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 = 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 = 1 ≡ 1 ≡ +1 (mod 17) であるため、1は17を法とする平方剰余である。
2 = 2 ≡ 256 ≡ +1 (mod 17) であるため、2は17を法とする平方剰余である。
3 = 3 ≡ 6561 ≡ −1 (mod 17) であるため、3は17を法とする平方剰余ではない。
4 = 4 ≡ 65536 ≡ +1 (mod 17) であるため、4は17を法とする平方剰余である。
5 = 5 ≡ 390625 ≡ −1 (mod 17) であるため、5は17を法とする平方剰余ではない。
これを16まで続けると、前述と同様に {1, 2, 4, 8, 9, 13, 15, 16} が平方剰余となる。
オイラーの規準は平方剰余の相互法則と関連する。
例 1: aが平方剰余になる奇素数pを見つける
a=3が平方剰余となる奇素数pを小さい方から求めてみる。
剰余が3であるから、pは4以上である。 また、pは素数なので5以上(5, 7, 11, ...)のみを判定すればよい。
ここでオイラーの規準を用いると、
p = 5を判定してみる。 3 = 3 ≡ 9 ≡ -1 (mod 5)となり、3は5を法とする平方剰余ではない。
p = 7を判定してみる。 3 = 3 ≡ 27 ≡ -1 (mod 7)となり、3は7を法とする平方剰余ではない。
p = 11を判定してみる。 3 = 3 ≡ 243 ≡ +1 (mod 11)となり、3は11を法とする平方剰余である。
p = 13を判定してみる。 3 = 3 ≡ 729 ≡ +1 (mod 13)となり、3は13を法とする平方剰余である。
p = 17を判定してみる。 3 = 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を法とする平方剰余はどの数であるか?
まずオイラーの規準を用いずに実際に計算してみると下記のようになる。
Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8
Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0-19-853171-5, https://archive.org/details/introductiontoth00hard
Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66957-4