オイラーの規準

出典: フリー百科事典『ウィキペディア(Wikipedia)』

数論において、オイラーの規準英語:Euler's criterion)は、ある整数が素数法とする平方剰余であるか否かを決定するための式である。

p素数とし、ap互いに素である整数とする。このとき[1][2][3]

オイラーの規準は、ルジャンドル記号を使用して簡潔に再定式化することができる[4]

この規準はレオンハルト・オイラーによる1748年の論文に初めて登場した[5][6]

証明[編集]

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

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

実際に、である。これはであるからである。 よって、 個の別個の平方剰余は である。

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

となり、これは

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

ここで a が平方剰余 ax2 であるとすると

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

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

[編集]

例 1: a が剰余である素数を見つける

a = 17とする。どの素数が p が17の平方剰余であるか?

上記の式を使用して、素数pを手計算で判定することができる。

ある場合、p = 3を判定すると、17(3 − 1)/2 = 171 ≡ 2 ≡ −1 (mod 3)となり、17は3を法とする平方剰余ではない。

別の場合、p = 13を判定すると、17(13 − 1)/2 = 176 ≡ 1 (mod 13)となり、17は13を法とする平方剰余である。確認として17 ≡ 4 (mod 13)であり、22 = 4である。

様々なモジュラ演算とルジャンドル記号の性質を使用することで、これらの計算をより高速に行うことができる。

値を計算し続けると、次のことが分かる。

(17/p) = +1 (p = {13, 19, ...}の場合)(17はこれらの値を法とした平方剰余である)
(17/p) = −1 (p = {3, 5, 7, 11, 23, ...}の場合)(17はこれらの値を法とした平方剰余でない)

例 2: 所与の素数の法 p の剰余を見つける

17を法とする平方数(17を法とする平方剰余)はどの数であるか?

実際に計算すると下記のようになる。

12 = 1
22 = 4
32 = 9
42 = 16
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 64 ≡ 13 (mod 17).

よって、17を法とする平方剰余のセットは {1,2,4,8,9,13,15,16} である。9から16までの値はすべてそれより前の平方数の値の負の数であるため (e.g. 9 ≡ −8 (mod 17)、よって92 ≡ (−8)2 = 64 ≡ 13 (mod 17))、平方数を計算する必要がない。

上式を使用することで平方剰余を見つけ出すまたはそれらを検証することができる。2が17を法とする平方剰余であるかどうかを判定するために、2(17 − 1)/2 = 28 ≡ 1 (mod 17)を計算し、平方剰余であると分かる。3が17を法とする平方剰余であるかどうかを判定するために、3(17 − 1)/2 = 38 ≡ 16 ≡ −1 (mod 17)を計算し、平方剰余でないと分かる。

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

応用[編集]

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

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

出典[編集]

  1. ^ Gauss, DA, Art. 106
  2. ^ 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 
  3. ^ Leonard Eugene Dickson, "History Of The Theory Of Numbers", vol 1, p 205, Chelsea Publishing 1952
  4. ^ Hardy & Wright, thm. 83
  5. ^ Lemmermeyer, p. 4 cites two papers, E134 and E262 in the Euler Archive
  6. ^ 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 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.

  • 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 

外部リンク[編集]