平方剰余の相互法則

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

平方剰余(へいほうじょうよ)とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則(へいほうじょうよのそうごほうそく、: quadratic reciprocity)は、ある整数 a が別の整数 p の平方剰余であるか否かを判定する法則である。

定義[編集]

整数 ap とが互いに素であるとする。合同式

が解を持つとき、 ap を法として平方剰余であるといい、そうでないとき平方非剰余であるという。

奇素数 p と、 p と互いに素な a に対して次の記号

を、平方剰余記号またはアドリアン=マリ・ルジャンドルにちなんでルジャンドル記号と呼ぶ。

相互法則[編集]

平方剰余の相互法則整数 a素数 p を法として平方剰余であるか否かを判定する法則である。

p, q を相異なる奇素数とするときに、
が成り立つ。

また、このほかに以下の第1補充法則、第2補充法則が知られている。

第1補充法則:

第2補充法則:

また、 p と互いに素な整数 a , b に対して

が成立する。一般に素数 p に対して Zp×={1,2,...,p-1} は p を法として乗法に関してになることが知られているが、この式は Zp× から{-1, 1}への群準同型写像が存在することを示している。よってその写像のは位数(p-1)/2の部分群となり、 Zp× の要素の半分は平方剰余であり、半分は平方非剰余であることが分かる。

この法則は、レオンハルト・オイラーによって予想され、カール・フリードリッヒ・ガウスによって証明された(ガウス日誌によれば、1796年4月8日。発表されたのは1801年の『整数論』において)。ガウスはこの法則に対して生涯で7つの異なる証明を与えた。その一つの動機は、三次や四次の相互法則を証明することにあった。現在では200近くもの証明が知られているが、どれもそれほど簡単ではない。

三次や四次の相互法則は、ヤコビアイゼンシュタインによって独立に証明された(1844年にアイゼンシュタインが証明を公表)。より高次のまた一般的な代数的整数における一般的な相互法則の証明は(ヒルベルトの第9問題)、高木貞治エミール・アルティンによってなされた。(アルティン相互法則を参照)

平方剰余の相互法則の応用[編集]

4k+1型の素数は二個の平方数の和で表すことができる。また逆にある奇素数が二つの平方数の和で表すことができるならば、4k+1型の素数である。

証明は、ある素数 p に対して と表せたならば r より真に小さいを選んで とできるアルゴリズムの存在を示すことで行うことができる。

4k+1型の素数は第1補充法則より、と表すことができるため、このアルゴリズムを適用すればいつかは r を 1 にすることができる。

平方剰余の計算[編集]

25以下の自然数 n 、50以下の素数 p について、n2 (mod p)を計算してみると次の表になる。

n2 (mod p) の計算表
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
n2 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625
mod 3 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1
mod 5 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0
mod 7 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2
mod 11 1 4 9 5 3 3 5 9 4 1 0 1 4 9 5 3 3 5 9 4 1 0 1 4 9
mod 13 1 4 9 3 12 10 10 12 3 9 4 1 0 1 4 9 3 12 10 10 12 3 9 4 1
mod 17 1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 0 1 4 9 16 8 2 15 13
mod 19 1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 0 1 4 9 16 6 17
mod 23 1 4 9 16 2 13 3 18 12 8 6 6 8 12 18 3 13 2 16 9 4 1 0 1 4
mod 29 1 4 9 16 25 7 20 6 23 13 5 28 24 22 22 24 28 5 13 23 6 20 7 25 16
mod 31 1 4 9 16 25 5 18 2 19 7 28 20 14 10 8 8 10 14 20 28 7 19 2 18 5
mod 37 1 4 9 16 25 36 12 27 7 26 10 33 21 11 3 34 30 28 28 30 34 3 11 21 33
mod 41 1 4 9 16 25 36 8 23 40 18 39 21 5 32 20 10 2 37 33 31 31 33 37 2 10
mod 43 1 4 9 16 25 36 6 21 38 14 35 15 40 24 10 41 31 23 17 13 11 11 13 17 23
mod 47 1 4 9 16 25 36 2 17 34 6 27 3 28 8 37 21 7 42 32 24 18 14 12 12 14

p = 3 の場合[編集]

となる。 q が 3 と異なる奇素数ならば、

と表せる。ここで、平方剰余の相互法則を使うと、

となり、

と求められる。今 q は 3 とも −1 とも互いに素であり、このことと第1補充法則より

と求められる。即ち、 3 と異なる奇素数 q に対して、 qx2+ 3 を割り切るような整数 x が存在することと、 q が 6 を法として 1 に合同であることは同値である。

p = 5 の場合[編集]

同様にして、qを 5 と異なる奇素数とすると、

ゆえに平方剰余の相互法則から

となり、よって

と求められる。

関連項目[編集]