代数の父と呼ばれるディオファントス(紀元200年頃実在）の著書 『算術』 ("Arithmetica") を 1621年にパシェが翻訳をして、それをフェルマー(1607-1665)が読んで、「数論」を構築したとされている。オイラー(1707-1783)は、『アリトメチカ論文集』を出して、ガウス(1777-1855)は『アリトメチカ研究』(1801年)という本を書いた。 「アリトメチカ"Arithmetica"」は、現代の「数論」へ名を変えて、発展していった。
ガウスは、『アリトメチカ研究』の中で、次の命題を証明している。
＜命題１＞
－１は、4n+1型の素数の平方剰余であり、4n+3型の素数の平方非剰余である。
この命題の具体的例を示す。
4n+1 型の素数には、例えば、 5,13,17,…がある。
5の平方剰余を求めてみる。
1²=1
2²=4≡-1
3²=9≡4≡-1
4²=16≡1
よって、平方剰余の中に、-1が含まれている。
13の平方剰余を求めてみる。
1²=1
2²=4
3²=9
4²=16≡13
5²=25≡12≡-1
6²=36≡1
7²=49 ≡10
であるので、やはり、-1が平方剰余になっている。
17の場合
1²=1
2²=4
3²=9
4²=16≡-1
5²=25≡8
6²=36≡2
7²=49 ≡15
8²=64 ≡13
であるので、やはり、-1が平方剰余になっている。
次に、4n+3 型の素数 3,7,11,… を調べてみよう。
3の場合
1²=1
2²=4≡1
平方剰余に 2≡-1はないので -1 は、平方非剰余である。
7の場合
1²=1
2²=4
3²=2
4²=2
平方剰余に6≡-1はないので、-1 は、平方非剰余である。
4n+1 型の素数でない数 例えば 9,21 について調べてみると
9の場合
1²=1
2²=4
3²=0
4²=16≡7
平方剰余に8≡-1はない。
21の場合
1²=1
2²=4
3²=9
4²=16
5²=25≡4
6²=36≡15
7²=49≡7
8²=64≡1
9²=81≡18
10²=100≡16
平方剰余に 21≡-1はない。
4n+3 型の素数でない数 15 について調べてみると
15の場合
1²=1
2²=4
3²=9
4²=16≡1
5²=25≡10
6²=36≡6
7²=49≡4
平方剰余に 14≡-1はない。
２を除く100までの24個の素数で
4n+1 型の素数は、5,13,17,29,37,41,53,61,73,89,97 で この素数のいずれにも -1が平方剰余として含まれている。一方で、4n+3型の素数の 3,7,11,19,23,31,43,47,59,67,71,79,83 には、平方剰余が -1になるものはない。
この＜命題１＞の証明は、「オイラーの基準」を使って簡単に証明できる。
「オイラーの規準」とは、以下のようなものである。
aがpの平方剰余ならば、a^(p-1)/2 ≡1 (mod p)
aがpの平方非剰余ならば、a^(p-1)/2 ≡-1 (mod p)
ルジャンドル記号
を使えば
と表すことができる。
具体例で説明しよう。
＜例＞
a=2, p=7 の場合
2は7の平方剰余であるので、 (2/7)=1 である。
2^(p-1)/2=2^(7-1)/2=2³=8≡1 (mod 7)
だから ※は、成り立つ。
a=3, p=7 の場合
3は7の平方非剰余であるので、 (3/7)=-1
3^(p-1)/2=3^(7-1)/2=3³=27≡6≡-1 (mod 7)
だから ※は、成り立つ。
a=2, p=5 の場合
2は5の平方非剰余であるので、 (2/5)=-1
2^(p-1)/2=2^(5-1)/2=2²=4≡-1 (mod 5)
だから ※は、成り立つ。
a=4, p=11 の場合
4は11の平方剰余だから (4/11)=1
4^(p-1)/2=4^(11-1)/2=4⁵≡1 (mod 11)
だから ※は、成り立つ。
a=3, p=17の場合
3は17の平方非剰余であるので、(3/7)=-1
3^(p-1)/2=3^(17-1)/2=3⁸≡16≡-1 (mod 17)
だから ※は、成り立つ。
オイラーの規準には、別な表現があるので、それを紹介しよう。
オイラーの規準は、
aがpの平方剰余ならば、a^(p-1)/2 ≡1 (mod p)
aがpの平方非剰余ならば、a^(p-1)/2 ≡-1 (mod p)
だった。
ここで
(p-1)/2 =m とすると
p=2m+1 になるので、以下のように表現できる。
素数 p=2m+1 で割り切れない数aについて、
aᵐ ≡1 (mod p) または、aᵐ ≡-1 (mod p) になる。
この表現にそって具体例で確かめてみよう。
m=3 で p=7 の場合
7 の平方剰余は、
1²=1
2²=4
3²=9≡2
4²=16≡2
5²=25≡4
6²=36≡1
より、1,2,4 である。非平方剰余は、3,5,6 である。
7でわれない数は、7n+1, 7n+2, 7n+3, 7n+4, 7n+5, 7n+6 である。
これらを a とすると 法を7 として
a³ =(7n+1)³≡1
a³ =(7n+2)³≡2³=8≡1
a³ =(7n+3)³≡3³=27≡6≡-1
a³ =(7n+4)³≡4³=64≡1
a³ =(7n+5)³≡5³=125≡6≡-1
a³ =(7n+6)³≡6³=216≡6≡-1
となって、確かに、aᵐ ≡±1 (mod p) になっている。
話はもどして、＜命題１＞の証明をしよう。
オイラーの規準より
aがpの平方剰余ならば、a^(p-1)/2 ≡1 (mod p)
p=4n+1 の平方剰余の中に -1 が含まれているとき
a=-1 であるので、
(-1)^(p-1)/2 で p=4n+1 とすると
(p-1)/2=4n/2=2n より、 (-1)^(2n)=1 になり、－１は、4n+1型の素数の平方剰余であることがわかる。
オイラーの規準より
aがpの平方非剰余ならば、a^(p-1)/2 ≡-1 (mod p)
p=4n+3 の平方非剰余の中に -1 が含まれているとき
a=-1 であるので
(-1)^(p-1)/2 で p=4n+3 とすると
(p-1)/2=(4n+2)/2=2n+1 より、(-1)^(2n+1)=-1 になり、-1は、4n+3型の素数の平方非剰余であることがわかる。