数論 において、オイラーの規準 （英語 ：Euler's criterion）は、ある整数が素数 を法とする 平方剰余 であるか否かを決定するための式である。
p を奇 素数とし、a を p と互いに素 である整数とする。このとき[ 1] [ 2] [ 3]
a
p
− − -->
1
2
≡ ≡ -->
{
1
(
mod
p
)
if there is an integer
x
such that
a
≡ ≡ -->
x
2
(
mod
p
)
,
− − -->
1
(
mod
p
)
if there is no such integer.
{\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}a\equiv x^{2}{\pmod {p}},\\-1{\pmod {p}}&{\text{ if there is no such integer.}}\end{cases}}}
オイラーの規準は、ルジャンドル記号 を使用して簡潔に再定式化することができる[ 4]
(
a
p
)
≡ ≡ -->
a
p
− − -->
1
2
(
mod
p
)
.
{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}
この規準はレオンハルト・オイラー による1748年の論文に初めて登場した[ 5] [ 6]
この証明は素数を法とする剰余のクラスが体 であることを使用する。詳細は素体の記事(en:Characteristic (algebra)#Case of fields )参照。
法が素数であるため、ラグランジュの定理 （英語版 ） k の多項式は最大で k 個の根しか持つことができない。特に、x 2 ≡ a (mod p )a に対して最大2つの解を持つ。このことは0の他にp を法とする少なくともp − 1/ 2 x の p − 1
実際に、
(
p
− − -->
x
)
2
≡ ≡ -->
x
2
(
mod
p
)
{\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}}
(
p
− − -->
x
)
2
≡ ≡ -->
p
2
− − -->
2
x
p
+
x
2
≡ ≡ -->
x
2
(
mod
p
)
{\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}}
p
− − -->
1
2
{\displaystyle {\tfrac {p-1}{2}}}
1
2
,
2
2
,
.
.
.
,
(
p
− − -->
1
2
)
2
(
mod
p
)
{\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}}
a は p と互いに素であるため、フェルマーの小定理 により
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 2
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 p ) がある（0以外）。よって、これらはきっかりと第1の因数をゼロにする剰余クラスである。もう1つの p − 1/ 2
例 1: a が平方剰余になる奇素数p を見つける
a =3が平方剰余となる奇素数p を小さい方から求めてみる。
剰余が3であるから、p は4以上である。
また、p は素数なので5以上(5, 7, 11, ...)のみを判定すればよい。
ここでオイラーの規準を用いると、
p = 5を判定してみる。 3(5 − 1)/2 = 32 ≡ 9 ≡ -1 (mod 5)となり、3は5を法とする平方剰余ではない。p = 7を判定してみる。 3(7 − 1)/2 = 33 ≡ 27 ≡ -1 (mod 7)となり、3は7を法とする平方剰余ではない。p = 11を判定してみる。 3(11 − 1)/2 = 35 ≡ 243 ≡ +1 (mod 11)となり、3は11を法とする平方剰余である。p = 13を判定してみる。 3(13 − 1)/2 = 36 ≡ 729 ≡ +1 (mod 13)となり、3は13を法とする平方剰余である。p = 17を判定してみる。 3(17 − 1)/2 = 38 ≡ 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を法とする平方剰余はどの数であるか？
まずオイラーの規準を用いずに実際に計算してみると下記のようになる。
12 = 1 ≡ 1 (mod 17)
22 = 4 ≡ 4 (mod 17)
32 = 9 ≡ 9 (mod 17)
42 = 16 ≡ 16 (mod 17)
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 64 ≡ 13 (mod 17). 残りの9から16までは、既に求めた8から1までと対称的に同じ値となるため、わざわざ求める必要はない。
(たとえば 11 ≡ −6 (mod 17) であるから、112 ≡ (−6)2 ≡ 62 ≡ 2 (mod 17))。
よって、17を法とする平方剰余のセットは {1, 2, 4, 8, 9, 13, 15, 16} と求められる。
これをオイラーの規準を使用することで求めてみる。
1(17 − 1)/2 = 18 ≡ 1 ≡ +1 (mod 17) であるため、1は17を法とする平方剰余である。
2(17 − 1)/2 = 28 ≡ 256 ≡ +1 (mod 17) であるため、2は17を法とする平方剰余である。
3(17 − 1)/2 = 38 ≡ 6561 ≡ −1 (mod 17) であるため、3は17を法とする平方剰余ではない。
4(17 − 1)/2 = 48 ≡ 65536 ≡ +1 (mod 17) であるため、4は17を法とする平方剰余である。
5(17 − 1)/2 = 58 ≡ 390625 ≡ −1 (mod 17) であるため、5は17を法とする平方剰余ではない。 これを16まで続けると、前述と同様に {1, 2, 4, 8, 9, 13, 15, 16} が平方剰余となる。
オイラーの規準は平方剰余の相互法則 と関連する。
実際には、ユークリッドの互除法 の拡張した変形を使用してヤコビ記号
(
a
n
)
{\displaystyle \left({\frac {a}{n}}\right)}
n
{\displaystyle n}
a
{\displaystyle a}
n
{\displaystyle n}
一方で、ヤコビ記号と
a
n
− − -->
1
2
{\displaystyle a^{\frac {n-1}{2}}}
ソロベイ–シュトラッセン素数判定法 として使用することができる。所与の
a
{\displaystyle a}
a
{\displaystyle a}
en:Euler–Jacobi pseudoprime )と呼ばれる。
^ Gauss , DA, Art. 106^ Dense, Joseph B.; Dence, Thomas P. (1999). “Theorem 6.4, Chap 6. Residues” . Elements of the Theory of Numbers . Harcourt Academic Press. p. 197. ISBN 9780122091308 . https://books.google.com/books?id=YiYHw7evhjkC&q=euler%27s+criterion+is+it+a+conditional+statement+or+a+biconditional+statement&pg=PA508 ^ Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952
^ Hardy & Wright, thm. 83
^ Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive
^ L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487
The Disquisitiones Arithmeticae Ciceronian Latin into English and German . The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity , the determination of the sign of the Gauss sum , the investigations into biquadratic reciprocity , and unpublished notes.
Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition) , New York: Springer , ISBN 0-387-96254-9 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
