平方剰余の相互法則の意味と応用

$x^2\equiv a\pmod{p}$

を満たす整数 $x$ が存在するとき，$a$ は $p$ の平方剰余であると言い，$\left(\dfrac{a}{p}\right)=1$ と書きます。

逆に，上記の合同式を満たす整数 $x$ が存在しないとき，$a$ は $p$ の平方剰余でないと言い，$\left(\dfrac{a}{p}\right)=-1$ と書きます。

→平方剰余と基本的な問題→ルジャンドル記号とオイラーの規準

「$x^2\equiv p\pmod{q}$ に解があるかどうか」

「$x^2\equiv q\pmod{p}$ に解があるかどうか」

のどちらか一方が分かればもう一方も分かるという素敵な定理です。

平方剰余の相互法則だけでは平方剰余かどうかを素早く判定することはできません。以下の補充法則が必要です。

$p$ を奇素数とする。

第一補充法則： $\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$

第二補充法則： $\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$

ルジャンドル記号の性質： $a,b$ が $p$ の倍数でないとき，$\left(\dfrac{ab}{p}\right)=\left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)$

第一補充法則とルジャンドル記号の性質はオイラーの規準から簡単に証明できます。→ルジャンドル記号とオイラーの規準

第二補充法則と相互法則（特に相互法則）の証明はけっこう大変です。例えば初等整数論講義などの本を参照して下さい。

これでいよいよ平方剰余の問題が解けます！

追記2015.9.15：平方剰余の相互法則のステートメントが間違っていましたので修正しました，申し訳ありませんでしたm(__)m