平方剰余の相互法則

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

## 定義
整数  と  とが互いに素であるとする。合同式
:x^2 \equiv a\pmod p
が解を持つとき、 は  を法として**平方剰余**であるといい、そうでないとき**平方非剰余**であるという。

### 平方剰余記号

奇素数  と、 と互いに素な整数  に対して、記号
:\left( \frac{a}{p} \right) :=
\begin{cases}
1  &\text{if } \exists x \in \mathbb{Z} [ x^2 \equiv a \pmod p ]\\
-1 &\text{if } \forall x \in \mathbb{Z} [ x^2 \not\equiv a \pmod p]
\end{cases}

を定める。

 と  が互いに素ではない場合、つまり整数  が奇素数  で割り切れる場合には、ｘ=0とすれば a は法ｐでｘの2乗と合同なのでaは平方剰余であるが、その場合にはむしろ記号の値を零とする方が都合の良いことがあるので、
:\left( \frac{a}{p} \right) := 0 
と定義することがある。

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

## 相互法則
**平方剰余の相互法則**は整数  が奇素数  を法として平方剰余であるか否かを判定する法則である。
:,  を相異なる奇素数とするときに、
::\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}}.

また、 と互いに素な整数 ,  に対して
::\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right)\left( \frac{b}{p} \right)
が成立する。一般に素数  に対して  は  を法とする乗法に関して群をなすが、この式はルジャンドル記号が  から への群準同型を与えることを示している。この写像の核は位数  の部分群であり、 の元のちょうど半分が平方剰余、残り半分が平方非剰余となる。

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

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

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

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

:
\begin{align}
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{align}


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

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

### 平方剰余の計算
 以下の自然数 ,  以下の素数  について、 を計算してみると次の表になる。

#### の場合
::\biggl( \frac{a}{3} \biggr) = \begin{cases}
  1  &\text{if }a \equiv 1\pmod 3\\
  -1 &\text{if }a \equiv 2\pmod 3\\
  0  &\text{if }a \equiv 0\pmod 3
\end{cases}
となる。 が  と異なる奇素数ならば、
::\biggl( \frac{q}{3} \biggr) = \begin{cases}
  1  &\text{if }q \equiv 1\pmod 6\\
  -1 &\text{if }q \equiv 5\pmod 6
\end{cases}
と表せる。ここで、**平方剰余の相互法則**を使うと、
::\biggl( \frac{3}{q} \biggr)\biggl( \frac{q}{3} \biggr) 
=(-1)^{\frac{3-1}{2} \cdot \frac{q-1}{2}} 
=(-1)^{\frac{q-1}{2}} 

となり、
::\left( \frac{3}{q} \right) = \begin{cases}
  1  &\text{if }q \equiv \pm 1\pmod {12}\\
  -1 &\text{if }q \equiv \pm 5\pmod {12}
\end{cases}
と求められる。今  は  とも  とも互いに素であり、このことと第1補充法則より
::\left( \frac{-3}{q} \right)
= \left(\frac{-1}{q} \right)\left( \frac{3}{q} \right)
= (-1)^{\frac{q-1}{2} \cdot 2} \biggl( \frac{q}{3} \biggr) 
= \biggl( \frac{q}{3} \biggr) 
= \begin{cases}
  1  &\text{if }q \equiv 1\pmod 6\\
  -1 &\text{if }q \equiv 5\pmod 6
\end{cases}
と求められる。即ち、 と異なる奇素数  に対して、 が  を割り切るような整数  が存在することと、 が  を法として  に合同であることは同値である。

#### の場合
同様にして、 を  と異なる奇素数とすると、
::\biggl( \frac{q}{5} \biggr) = \begin{cases}
  1  &\text{if }q \equiv \pm 1\pmod 5\\
  -1 &\text{if }q \equiv \pm 2\pmod 5.
\end{cases}
ゆえに**平方剰余の相互法則**から
::\biggl( \frac{5}{q} \biggr)\biggl( \frac{q}{5} \biggr) 
= (-1)^{ \frac{5-1}{2} \cdot \frac{q-1}{2} } 
= 1 

となり、よって
::\left( \frac{5}{q} \right) = \begin{cases}
  1  &\text{if }q \equiv \pm 1\pmod 5\\
  -1 &\text{if }q \equiv \pm 2\pmod 5
\end{cases}
と求められる。

## 脚注

## 参考文献
* 久保田富雄：「数の幾何学と類体論」、(名古屋大学数学レクチャーノート、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日).
*

## 関連項目

* 
* 
* Disquisitiones Arithmeticae

## 外部リンク
*
*
*
*
*Gaussの和を使った具体例　https://ameblo.jp/titchmarsh/entry-12568067829.html
*平方剰余とGaussの和を使った具体例　https://ameblo.jp/titchmarsh/entry-12568052621.html