平方剰余の相互法則

thumb|ガウスは『整数論』（1801年）で平方剰余の相互法則の最初の証明を公開した。（へいほうじょうよ、）とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則（へいほうじょうよのそうごほうそく、）は、ある整数が別の整数の平方剰余であるか否かを判定する法則である。

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

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

平方剰余記号

奇素数と、と互いに素な整数に対して、記号

を定める。

とが互いに素ではない場合、つまり整数が奇素数で割り切れる場合には、ｘ=0とすれば a は法ｐでｘの2乗と合同なのでaは平方剰余であるが、その場合にはむしろ記号の値を零とする方が都合の良いことがあるので、

と定義することがある。

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

相互法則平方剰余の相互法則は整数が奇素数を法として平方剰余であるか否かを判定する法則である。 , を相異なる奇素数とするときに、

が成り立つ。

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

第1補充法則:

第2補充法則:

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

が成立する。一般に素数に対してはを法とする乗法に関して群をなすが、この式はルジャンドル記号がからへの群準同型を与えることを示している。この写像の核は位数の部分群であり、の元のちょうど半分が平方剰余、残り半分が平方非剰余となる。

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

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

平方剰余の相互法則の応用フェルマーの二平方和の定理

型の素数は二個の平方数の和で表すことができる。また逆にある奇素数が二つの平方数の和で表すことができるならば、型の素数である。そして、二つの平方数の順序を別にすればこの分解は一意的である。

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

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

平方剰余の計算以下の自然数 , 以下の素数について、を計算してみると次の表になる。 + n2 (mod p) の計算表 n 12 3 45 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 n2 1 491625364964 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 1625 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 1625 36 12 27 7 2610 33 21 11 3 34 30 28 28 30 34 3 11 21 33 mod 41 1 4 9 1625 36 8 23 40 183921 5 32 20 10 2 37 33 31 31 33 37 2 10 mod 43 1 4 9 1625 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 1625 36 2 17 34 6 27 3 28 8 3721742322418 14 12 12 14

の場合

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

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

となり、

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

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

の場合同様にして、をと異なる奇素数とすると、

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

となり、よって

と求められる。

脚注

参考文献久保田富雄：「数の幾何学と類体論」、(名古屋大学数学レクチャーノート、no.8）、Department of Mathematics、Nagoya University（1985年）。一般の冪剰余の相互法則を扱う。

平松豊一：「数論を学ぶ人のための相互法則入門」、牧野書店、ISBN 4-7952-0120-X (1998年5月10日). 久保田富雄：「数論論説：メタプレクティック理論と幾何学的相互法則」、牧野書店、ISBN 4-79520129-3 (1999年11月). ※ 高次相互法則を扱う。

※ ガウスの与えた7通りの証明を解説。

西来路文朗、清水健一：「ガウスの黄金定理 : 平方剰余の相互法則で語る数論の世界」、講談社 (ブルーバックス 2243)、ISBN 978-4-06-533542-0 (2023年10月19日).

平方剰余の相互法則

Źródło i licencja