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

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

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

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

奇素数 p と、p と互いに素な整数 a に対して、記号 ( a p ) := { 1 if  ∃ x ∈ Z [ x 2 ≡ a ( mod p ) ] − 1 if  ∀ x ∈ Z [ x 2 ≢ a ( mod p ) ] {\displaystyle \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}}}

を定める。

奇素数 p で割り切れるような整数 a に対しても ( a p ) := 0 {\displaystyle \left({\frac {a}{p}}\right):=0}

と定めておくことがある。

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

平方剰余の相互法則は整数 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)}

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

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

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

4k + 1 型の素数は二個の平方数の和で表すことができる。また逆にある奇素数が二つの平方数の和で表すことができるならば、4k + 1 型の素数である。そして、二つの平方数の順序を別にすればこの分解は一意的である。 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 . {\displaystyle {\begin{aligned}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{aligned}}}