平方剰余（へいほうじょうよ）とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則（へいほうじょうよのそうごほうそく、）は、ある整数 が別の整数 の平方剰余であるか否かを判定する法則である。整数 と とが互いに素であるとする。合同式が解を持つとき、 は を法として平方剰余であるといい、そうでないとき平方非剰余であるという。奇素数 と、 と互いに素な に対して次の記号を、平方剰余記号、またはアドリアン＝マリ・ルジャンドルにちなんでルジャンドル記号と呼ぶ。平方剰余の相互法則は整数 が奇素数 を法として平方剰余であるか否かを判定する法則である。また、このほかに以下の第1補充法則、第2補充法則が知られている。第1補充法則:第2補充法則:また、 と互いに素な整数 , に対してが成立する。一般に素数 に対して は を法として乗法に関して群になることが知られているが、この式は から への群準同型写像が存在することを示している。よってその写像の核は位数 の部分群となり、 の要素の半分は平方剰余であり、半分は平方非剰余であることが分かる。この法則は、レオンハルト・オイラーによって予想され、カール・フリードリッヒ・ガウスによって証明された（ガウス日誌によれば、1796年4月8日。発表されたのは1801年の『整数論』において）。ガウスはこの法則に対して生涯で7つの異なる証明を与えた。その一つの動機は、三次や四次の相互法則を証明することにあった。現在では200近くもの証明が知られているが、どれもそれほど簡単ではない。三次や四次の相互法則は、ヤコビ、アイゼンシュタインによって独立に証明された（1844年にアイゼンシュタインが証明を公表）。より高次のまた一般的な代数的整数における一般的な相互法則の証明は（ヒルベルトの第9問題）、高木貞治やエミール・アルティンによってなされた。（アルティン相互法則を参照） 型の素数は二個の平方数の和で表すことができる。また逆にある奇素数が二つの平方数の和で表すことができるならば、 型の素数である。formula_7証明は、ある素数 に対して と表せたならば より真に小さい を選んで とできるアルゴリズムの存在を示すことで行うことができる。 以下の自然数 , 以下の素数 について、 を計算してみると次の表になる。となる。 が と異なる奇素数ならば、と表せる。ここで、平方剰余の相互法則を使うと、となり、と求められる。今 は とも とも互いに素であり、このことと第1補充法則よりと求められる。即ち、 と異なる奇素数 に対して、 が を割り切るような整数 が存在することと、 が を法として に合同であることは同値である。同様にして、 を と異なる奇素数とすると、ゆえに平方剰余の相互法則からとなり、よってと求められる。

出典:wikipedia