この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。
出典検索?: "平方剰余の相互法則" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2016年6月）
ガウスは『整数論』（1801年）で平方剰余の相互法則の最初の証明を公開した。

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

1 定義

2 相互法則

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

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

3.2 平方剰余の計算

3.2.1 p = 3 の場合

3.2.2 p = 5 の場合



4 脚注

5 参考文献

6 関連項目

7 外部リンク

定義

整数 a と p とが互いに素であるとする。合同式 x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}}

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

奇素数 p と整数 a に対して、次の記号 ( a p ) := { 1 if  a ≢ 0 ∧ ( ∃ x )   x 2 ≡ a ( mod p ) − 1 if  ( ∀ x )   x 2 ≢ a ( mod p ) 0 if    a ≡ 0 ( mod p ) {\displaystyle \left({\frac {a}{p}}\right):={\begin{cases}1&{\text{if }}a\not \equiv 0\land (\exists x)\ x^{2}\equiv a{\pmod {p}}\\-1&{\text{if }}(\forall x)\ x^{2}\not \equiv a{\pmod {p}}\\0&{\text{if }}\ a\equiv 0{\pmod {p}}\end{cases}}}

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

平方剰余の相互法則は整数 a が奇素数 p を法として平方剰余であるか否かを判定する法則である。p, q を相異なる奇素数とするときに、 ( p q ) ( q p ) = ( − 1 ) p − 1 2 ⋅ q − 1 2 {\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}} が成り立つ。

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

第1補充法則: ( − 1 p ) = ( − 1 ) p − 1 2 . {\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}.}

第2補充法則: ( 2 p ) = ( − 1 ) p 2 − 1 8 . {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}.}

また、p と互いに素な整数 a, b に対して ( a b p ) = ( a p ) ( b p ) {\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)}