平方剰余の相互法則

ガウスは『整数論』（1801年）で平方剰余の相互法則の最初の証明を公開した。

テンプレート:仮リンク（へいほうじょうよ、テンプレート:Lang-en-short）とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則（へいほうじょうよのそうごほうそく、テンプレート:Lang-en-short）は、ある整数 テンプレート:Mvar が別の整数 テンプレート:Mvar の平方剰余であるか否かを判定する法則である。

定義

整数 テンプレート:Mvar と テンプレート:Mvar とが互いに素であるとする。合同式

$x^2\equiv a(\mathrm{mod}p)$

が解を持つとき、テンプレート:Mvar は テンプレート:Mvar を法として平方剰余であるといい、そうでないとき平方非剰余であるという。

平方剰余記号

奇素数 テンプレート:Mvar と、テンプレート:Mvar と互いに素な整数 テンプレート:Mvar に対して、記号

$\left(\frac{a}{p}\right):=\{\begin{array}{cc}1& \text{if }\mathrm{\exists }x\in \mathbb{Z}[x^2\equiv a(\mathrm{mod}p)]\\ -1& \text{if }\mathrm{\forall }x\in \mathbb{Z}[x^2\equiv ̸a(\mathrm{mod}p)]\end{array}$

を定める。

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

$\left(\frac{a}{p}\right):=0$

と定義することがある。

記号 $\left(\frac{a}{p}\right)$ を、平方剰余記号、またはアドリアン＝マリ・ルジャンドルにちなんでルジャンドル記号と呼ぶ。

相互法則

平方剰余の相互法則は整数 テンプレート:Mvar が奇素数 テンプレート:Mvar を法として平方剰余であるか否かを判定する法則である。

テンプレート:Mvar, テンプレート:Mvar を相異なる奇素数とするときに、

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$

が成り立つ。

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

第1補充法則:

$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}.$

第2補充法則:

$\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}.$

また、テンプレート:Mvar と互いに素な整数 テンプレート:Mvar, テンプレート:Mvar に対して

$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

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

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

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

平方剰余の相互法則の応用

フェルマーの二平方和の定理

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

$\begin{array}{cccccccc}5& =1^2+2^2,& 113& =7^2+8^2,& 277& =9^2+14^2,& 421& =14^2+15^2,\\ 13& =2^2+3^2,& 137& =4^2+11^2,& 281& =5^2+16^2,& 433& =12^2+17^2,\\ 17& =1^2+4^2,& 149& =7^2+10^2,& 293& =2^2+17^2,& 449& =7^2+20^2,\\ 29& =2^2+5^2,& 157& =6^2+11^2,& 313& =12^2+13^2,& 457& =4^2+21^2,\\ 37& =1^2+6^2,& 173& =2^2+13^2,& 317& =11^2+14^2,& 461& =10^2+19^2,\\ 41& =4^2+5^2,& 181& =9^2+10^2,& 337& =9^2+16^2,& 509& =5^2+22^2,\\ 53& =2^2+7^2,& 193& =7^2+12^2,& 349& =5^2+18^2,& 521& =11^2+20^2,\\ 61& =5^2+6^2,& 197& =1^2+14^2,& 353& =8^2+17^2,& 541& =10^2+21^2,\\ 73& =3^2+8^2,& 229& =2^2+15^2,& 373& =7^2+18^2,& 557& =14^2+19^2,\\ 89& =5^2+8^2,& 233& =8^2+13^2,& 389& =10^2+17^2,& 569& =13^2+20^2,\\ 97& =4^2+9^2,& 241& =4^2+15^2,& 397& =6^2+19^2,& 577& =1^2+24^2,\\ 101& =1^2+10^2,& 257& =1^2+16^2,& 401& =1^2+20^2,& 593& =8^2+23^2,\\ 109& =3^2+10^2,& 269& =10^2+13^2,& 409& =3^2+20^2,& 601& =5^2+24^2.\end{array}$

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

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

平方剰余の計算

テンプレート:Math 以下の自然数 テンプレート:Mvar, テンプレート:Math 以下の素数 テンプレート:Mvar について、テンプレート:Math を計算してみると次の表になる。

n² (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

テンプレート:Math の場合

$\left(\frac{a}{3}\right)=\{\begin{array}{cc}1& \text{if }a\equiv 1(\mathrm{mod}3)\\ -1& \text{if }a\equiv 2(\mathrm{mod}3)\\ 0& \text{if }a\equiv 0(\mathrm{mod}3)\end{array}$

となる。テンプレート:Mvar が テンプレート:Math と異なる奇素数ならば、

$\left(\frac{q}{3}\right)=\{\begin{array}{cc}1& \text{if }q\equiv 1(\mathrm{mod}6)\\ -1& \text{if }q\equiv 5(\mathrm{mod}6)\end{array}$

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

$\left(\frac{3}{q}\right)\left(\frac{q}{3}\right)=(-1{)}^{\frac{3-1}{2}\cdot \frac{q-1}{2}}=(-1{)}^{\frac{q-1}{2}}$

となり、

$\left(\frac{3}{q}\right)=\{\begin{array}{cc}1& \text{if }q\equiv \pm 1(\mathrm{mod}12)\\ -1& \text{if }q\equiv \pm 5(\mathrm{mod}12)\end{array}$

と求められる。今 テンプレート:Mvar は テンプレート:Math とも テンプレート:Math とも互いに素であり、このことと第1補充法則より

$\left(\frac{-3}{q}\right)=\left(\frac{-1}{q}\right)\left(\frac{3}{q}\right)=(-1{)}^{\frac{q-1}{2}\cdot 2}(\frac{q}{3})=(\frac{q}{3})=\{\begin{array}{cc}1& \text{if }q\equiv 1(\mathrm{mod}6)\\ -1& \text{if }q\equiv 5(\mathrm{mod}6)\end{array}$

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

テンプレート:Math の場合

同様にして、テンプレート:Mvar を テンプレート:Math と異なる奇素数とすると、

$\left(\frac{q}{5}\right)=\{\begin{array}{cc}1& \text{if }q\equiv \pm 1(\mathrm{mod}5)\\ -1& \text{if }q\equiv \pm 2(\mathrm{mod}5).\end{array}$

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

$\left(\frac{5}{q}\right)\left(\frac{q}{5}\right)=(-1{)}^{\frac{5-1}{2}\cdot \frac{q-1}{2}}=1$

となり、よって

$\left(\frac{5}{q}\right)=\{\begin{array}{cc}1& \text{if }q\equiv \pm 1(\mathrm{mod}5)\\ -1& \text{if }q\equiv \pm 2(\mathrm{mod}5)\end{array}$

と求められる。

参考文献

• 久保田富雄：「数の幾何学と類体論」、(名古屋大学数学レクチャーノート、no.8）、Department of Mathematics、Nagoya University（1985年）。一般の冪剰余の相互法則を扱う。
• テンプレート:Cite book
• 平松豊一：「数論を学ぶ人のための相互法則入門」、牧野書店、ISBN 4-7952-0120-X (1998年5月10日).
• 久保田富雄：「数論論説：メタプレクティック理論と幾何学的相互法則」、牧野書店、ISBN 4-79520129-3 (1999年11月). ※ 高次相互法則を扱う。
• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book ※ ガウスの与えた7通りの証明を解説。
• テンプレート:Cite book
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book
• 西来路文朗、清水健一：「ガウスの黄金定理 : 平方剰余の相互法則で語る数論の世界」、講談社 (ブルーバックス 2243)、ISBN 978-4-06-533542-0 (2023年10月19日).
• テンプレート:Citation

関連項目

• テンプレート:仮リンク
• テンプレート:仮リンク
• Disquisitiones Arithmeticae

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:PDFlink
• テンプレート:PDFlink
• テンプレート:MathWorld
• Gaussの和を使った具体例　https://ameblo.jp/titchmarsh/entry-12568067829.html
• 平方剰余とGaussの和を使った具体例　https://ameblo.jp/titchmarsh/entry-12568052621.html