オイラーの規準

数論において、オイラーの規準（英語：Euler's criterion）は、ある整数が素数を法とする平方剰余であるか否かを決定するための式である。
"p" を奇素数とし、"a" を "p" と互いに素である整数とする。このとき
オイラーの規準は、ルジャンドル記号を使用して簡潔に再定式化することができる。
この規準はレオンハルト・オイラーによる1748年の論文に初めて登場した。
証明.
この証明は素数を法とする剰余のクラスが体であることを使用する。詳細は素体の記事()参照。
法が素数であるため、が適用される。次数 の多項式は最大で 個の根しか持つことができない。特に、 は各 に対して最大2つの解を持つ。このことは0の他にを法とする少なくとも個の異なる平方剰余があることを即座に意味する。 の 個の可能な値の各々は、同じ剰余を与えるために互いに付随することしかできない。
実際に、formula_3である。これはformula_4であるからである。
よって、formula_5 個の別個の平方剰余は
formula_6である。
 は と互いに素であるため、フェルマーの小定理により
となり、これは
と書くことができる。
 を法とする整数は体を形成するため、それぞれの についてこれらの因数のいずれかがゼロでなければならない。
ここで が平方剰余 であるとすると
となる。よって平方剰余 (mod ) により第1の因数がゼロになる。
ラグランジュの定理を再度適用すると、第1の因数をゼロにするの値は より多くはないことに留意する。しかし、最初に述べたように少なくとも 個の異なる平方剰余 (mod ) がある（0以外）。よって、これらはきっかりと第1の因数をゼロにする剰余クラスである。もう1つの 個の剰余クラス（非剰余）は2番目の因数がゼロである必要があり、そうでないとフェルマーの小定理を満たさない。これがオイラーの規準である。
例.
例 1: "a"が平方剰余になる奇素数"p"を見つける
"a"=3が平方剰余となる奇素数"p"を小さい方から求めてみる。
剰余が3であるから、"p"は4以上である。
また、"p"は素数なので5以上(5, 7, 11, ...)のみを判定すればよい。
ここでオイラーの規準を用いると、
値を計算し続けると、次の結果となる(括弧はルジャンドル記号)。
例 2: 与えられた奇素数"p"を法とする平方剰余を見つける
奇素数"p"=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} と求められる。
これをオイラーの規準を使用することで求めてみる。
これを16まで続けると、前述と同様に {1, 2, 4, 8, 9, 13, 15, 16} が平方剰余となる。
オイラーの規準は平方剰余の相互法則と関連する。
応用.
実際には、ユークリッドの互除法の拡張した変形を使用してヤコビ記号 formula_10 を計算する方が効率的である。formula_11 が奇素数である場合、これはルジャンドル記号と等しく、 formula_12 が formula_11 を法とする平方剰余であるかどうかを決定する。
一方で、ヤコビ記号とformula_14の同等性は全ての奇素数に当てはまるが、必ずしも合成数には当てはまらないため、両方を計算してそれらを比較することで素数判定、特にソロベイ–シュトラッセン素数判定法として使用することができる。所与のformula_12に対して合同が成り立つ合成数は、底 formula_12 に対するオイラー・ヤコビ擬素数()と呼ばれる。
レファレンス.
The "Disquisitiones Arithmeticae" has been translated from Gauss's 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.