平方剰余の相互法則（など）を用いることで，与えられた素数 $p$ と $p$ 未満の非負整数 $a$ に対して $p$ で割って $a$ 余るような平方数が存在するか否かを素早く判定することができる。
平方剰余の相互法則の意味と応用について解説します。
前提知識
$x^2\equiv a\:\mathrm{mod}\:p$
を満たす整数 $x$ が存在するとき，$a$ は $p$ の平方剰余であると言い，$\left(\dfrac{a}{p}\right)=1$ と書きます。
逆に，上記の合同式を満たす整数 $x$ が存在しないとき，$a$ は $p$ の平方剰余でないと言い，$\left(\dfrac{a}{p}\right)=-1$ と書きます。
→平方剰余と基本的な問題
→ルジャンドル記号とオイラーの規準
平方剰余の相互法則
平方剰余の相互法則：相異なる奇素数 $p,q$ に対して
$\left(\dfrac{q}{p}\right)\left(\dfrac{p}{q}\right)=(-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$
「 $x^2\equiv p\:\mathrm{mod}\:q$ に解があるかどうか」
「 $x^2\equiv q\:\mathrm{mod}\: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)$
第一補充法則とルジャンドル記号の性質はオイラーの規準から簡単に証明できます。→ルジャンドル記号とオイラーの規準
第二補充法則と相互法則（特に相互法則）の証明はけっこう大変です。例えば初等整数論講義などの本を参照して下さい。
具体例
これでいよいよ平方剰余の問題が解けます！
例題
$19$ で割って $14$ 余る平方数は存在するか判定せよ。
解答
$\left(\dfrac{14}{19}\right)=\left(\dfrac{2}{19}\right)\left(\dfrac{7}{19}\right)$（ルジャンドル記号の性質）
- $\left(\dfrac{2}{19}\right)=(-1)^{45}=-1$（第二補充法則）
- $\left(\dfrac{7}{19}\right)=(-1)^{3\cdot 9}\left(\dfrac{19}{7}\right)=-\left(\dfrac{19}{7}\right)$（相互法則）
さらに相互法則と第二補充法則を使うと，
$-\left(\dfrac{19}{7}\right)=-\left(\dfrac{5}{7}\right)=-(-1)^{2\cdot 3}\left(\dfrac{7}{5}\right)\\=-\left(\dfrac{2}{5}\right)=-(-1)^3=1$
以上より $\left(\dfrac{14}{19}\right)=-1$ となるので，$19$ で割って $14$ 余る平方数は存在しない。
注：この例題なら普通に $1^2$ から $18^2$ まで（本当は $9^2$ まででよい）計算してもあまりスピードは変わりませんが，これがもっと大きい数字になると（例えば $17117$ で割って $345$ 余る平方数は存在するか判定せよとか）上記の手法のありがたみが実感できます。
追記2015.9.15：平方剰余の相互法則のステートメントが間違っていましたので修正しました，申し訳ありませんでしたm(__)m