オイラーの規準のソースを表示

[[数論]]において、'''オイラーの規準'''（[[英語]]：Euler's criterion）は、ある整数が[[素数]]を[[合同算術|法とする]][[平方剰余]]であるか否かを決定するための式である。

''p'' を[[奇数|奇]]素数とし、''a'' を ''p'' と[[互いに素 (整数論)|互いに素]]である整数とする。このとき<ref>[[Gauss]], DA, Art. 106</ref><ref>{{cite book|first1 = Joseph B. | last1 = Dense | first2 = Thomas P. | last2 = Dence | title = Elements of the Theory of Numbers | chapter = Theorem 6.4, Chap 6. Residues | page = 197 | publisher = Harcourt Academic Press | year = 1999 | isbn = 9780122091308 | chapter-url = https://books.google.com/books?id=YiYHw7evhjkC&q=euler%27s+criterion+is+it+a+conditional+statement+or+a+biconditional+statement&pg=PA508}}</ref><ref>Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952</ref>

:<math>
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}
</math>

オイラーの規準は、[[ルジャンドル記号]]を使用して簡潔に再定式化することができる<ref>Hardy & Wright, thm. 83</ref>。
:<math>
\left(\frac{a}{p}\right) \equiv a^{\tfrac{p-1}{2}} \pmod p.
</math>

この規準は[[レオンハルト・オイラー]]による1748年の論文に初めて登場した<ref>Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive</ref><ref>L Euler, Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, 8, 1760-1, 74; Opusc Anal. 1, 1772, 121; Comm. Arith, 1, 274, 487</ref>。

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

法が素数であるため、{{仮リンク|ラグランジュの定理 (数論)|en|Lagrange's theorem (number theory)|label=ラグランジュの定理}}が適用される。次数 {{mvar|k}} の多項式は最大で {{mvar|k}} 個の根しか持つことができない。特に、{{math|''x''{{sup|2}} &equiv; ''a'' (mod ''p'')}} は各 {{mvar|a}} に対して最大2つの解を持つ。このことは0の他に{{mvar|p}}を法とする少なくとも{{math|{{sfrac|''p'' − 1|2}}}}個の異なる平方剰余があることを即座に意味する。{{mvar|x}} の {{math|''p'' − 1}} 個の可能な値の各々は、同じ剰余を与えるために互いに付随することしかできない。

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

{{mvar|a}} は {{mvar|p}} と互いに素であるため、[[フェルマーの小定理]]により
:<math>
a^{p-1}\equiv 1 \pmod p,
</math>
となり、これは
:<math>
\left( a^{\tfrac{p-1}{2}}-1 \right)\left( a^{\tfrac{p-1}{2}}+1 \right)    \equiv 0 \pmod p.
</math>
と書くことができる。
{{mvar|p}} を法とする整数は体を形成するため、それぞれの {{mvar|a}} についてこれらの因数のいずれかがゼロでなければならない。

ここで {{mvar|a}} が平方剰余 {{math|''a'' ≡ ''x''<sup>2</sup>}} であるとすると
:<math>
a^{\tfrac{p-1}{2}}\equiv {(x^2)}^{\tfrac{p-1}{2}} \equiv x^{p-1}\equiv1\pmod p.
</math>
となる。よって平方剰余 (mod {{mvar|p}}) により第1の因数がゼロになる。

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

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

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

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

ここでオイラーの規準を用いると、
: ''p'' = 5を判定してみる。 3<sup>(5 − 1)/2</sup> = 3<sup>2</sup> ≡ 9 ≡ -1 (mod 5)となり、3は5を法とする平方剰余ではない。
: ''p'' = 7を判定してみる。 3<sup>(7 − 1)/2</sup> = 3<sup>3</sup> ≡ 27 ≡ -1 (mod 7)となり、3は7を法とする平方剰余ではない。
: ''p'' = 11を判定してみる。 3<sup>(11 − 1)/2</sup> = 3<sup>5</sup> ≡ 243 ≡ +1 (mod 11)となり、3は11を法とする平方剰余である。
: ''p'' = 13を判定してみる。 3<sup>(13 − 1)/2</sup> = 3<sup>6</sup> ≡ 729 ≡ +1 (mod 13)となり、3は13を法とする平方剰余である。
: ''p'' = 17を判定してみる。 3<sup>(17 − 1)/2</sup> = 3<sup>8</sup> ≡ 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<sup>2</sup> = 1 ≡ 1 (mod 17)
: 2<sup>2</sup> = 4 ≡ 4 (mod 17)
: 3<sup>2</sup> = 9 ≡ 9 (mod 17)
: 4<sup>2</sup> = 16 ≡ 16 (mod 17)
: 5<sup>2</sup> = 25 ≡ 8 (mod 17)
: 6<sup>2</sup> = 36 ≡ 2 (mod 17)
: 7<sup>2</sup> = 49 ≡ 15 (mod 17)
: 8<sup>2</sup> = 64 ≡ 13 (mod 17).
残りの9から16までは、既に求めた8から1までと対称的に同じ値となるため、わざわざ求める必要はない。

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

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

これをオイラーの規準を使用することで求めてみる。
: 1<sup>(17 − 1)/2</sup> = 1<sup>8</sup> ≡ 1 ≡ +1 (mod 17) であるため、1は17を法とする平方剰余である。
: 2<sup>(17 − 1)/2</sup> = 2<sup>8</sup> ≡ 256 ≡ +1 (mod 17) であるため、2は17を法とする平方剰余である。
: 3<sup>(17 − 1)/2</sup> = 3<sup>8</sup> ≡ 6561 ≡ −1 (mod 17) であるため、3は17を法とする平方剰余ではない。
: 4<sup>(17 − 1)/2</sup> = 4<sup>8</sup> ≡ 65536 ≡ +1 (mod 17) であるため、4は17を法とする平方剰余である。
: 5<sup>(17 − 1)/2</sup> = 5<sup>8</sup> ≡ 390625 ≡ −1 (mod 17) であるため、5は17を法とする平方剰余ではない。
これを16まで続けると、前述と同様に {1, 2, 4, 8, 9, 13, 15, 16} が平方剰余となる。

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

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

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

==出典==

{{reflist}}

==レファレンス==

The ''[[Disquisitiones Arithmeticae]]'' has been translated from Gauss's [[Classical Latin|Ciceronian Latin]] into [[English language|English]] and [[German language|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.

*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Clarke | first2 = Arthur A. (translator into English)  
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | year = 1986
  | isbn = 0-387-96254-9}}

*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Maser | first2 = H. (translator into German)  
  | title = Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
  | publisher = Chelsea
  | location = New York
  | year = 1965
  | isbn = 0-8284-0191-8}}

*{{citation |last1      = Hardy
 |first1     = G. H.
 |last2      = Wright
 |first2     = E. M.
|author1link = G. H. Hardy
|author2link = E. M. Wright
 |title      = An Introduction to the Theory of Numbers (Fifth edition)
 |publisher  = [[Oxford University Press]]
 |location   = Oxford
 |year       = 1980
 |isbn       = 978-0-19-853171-5
 |url-access = registration
 |url        = https://archive.org/details/introductiontoth00hard
}}

*{{citation
  | last1 = Lemmermeyer  | first1 = Franz
  | title = Reciprocity Laws: from Euler to Eisenstein
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 2000
  | isbn = 3-540-66957-4}}

==外部リンク==
*[http://www.math.dartmouth.edu/~euler/index.html The Euler Archive]
*{{SpringerEOM|title=Euler criterion|urlname=Euler_criterion}}

{{DEFAULTSORT:おいらあのきしゆん}}
[[Category:合同算術]]
[[Category:平方剰余]]
[[Category:数論の定理]]
[[Category:素数]]
[[Category:レオンハルト・オイラー]]
[[Category:数学に関する記事]]