p を奇素数、a を p で割り切れない数、x^2 \equiv a \pmod{p} としたときに解を持つ、持たないにしたがって a を p の平方剰余、平方非剰余 という。
a \not\equiv 0 のとき a が平方剰余、非剰余にしたがって
\left( \frac{a}{p} \right) = 1, \, -1 とする。また、便宜上 \left(\frac{kp}{p}\right)=0 とする。これをルジャンドル記号と呼ぶ。
したがって \left(\frac{a}{p}\right) は a の属する剰余類にのみ依存する。そして \left(\frac{a}{p}\right)=-1 ならば kp+a の形の平方数は存在しない。
例 \left(\frac{2}{3}\right)=\left(\frac{3}{4}\right)=\left(\frac{3}{5}\right)=-1, \left(\frac{4}{5}\right)=1 である。
補題 1
r を p の原始根とする。定理 2.3.4 から x^2 \equiv a \pmod{p} が解を持つのと {\rm Ind}_r \, a が (2, p-1) = 2 で割り切れるというのは同値である。したがって
\left( \frac{a}{p} \right) = (-1)^{{\rm Ind}_r \, a}.
a \equiv a' \pmod{p} ならば \left( \frac{a}{p} \right) = \left( \frac{a'}{p} \right)
証明
合同の推移性、または補題 1 によって明白。
\left( \frac{abc\cdots}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) \left( \frac{c}{p} \right) \cdots
証明
補題 1 より \left( \frac{abc\cdots}{p} \right) = (-1)^{{\rm Ind}_r \, abc\cdots}
定理 2.3.4 より 、これは
(-1)^{{\rm Ind}_r \, a \ + {\rm Ind}_r \  b \ + {\rm Ind}_r \, c \ + \cdots} (-1)^{{\rm Ind}_r \, a} \ (-1)^{{\rm Ind}_r \, b} \ =(-1)^{{\rm Ind}_r \, c} \cdots
に等しい。ここで再び補題 1 より、これは
= \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) \left( \frac{c}{p} \right) \cdots
に等しい。
 \pmod{p}
証明 1
定理 2.3.4 から x^2 \equiv a \pmod{p} が解を持つ、つまり \left( \frac{a}{p} \right) = 1 のとき、
f = \frac{p-1}{(2, p-1)}, \ \ a^f \equiv 1 \pmod{p}.
 \equiv 1 \pmod{p}
したがって \left( \frac{a}{p} \right) \equiv 1 \pmod{p}.
逆に \left( \frac{a}{p} \right) = -1 、つまり x^2 \equiv a \pmod{p} が解を持たないとき、再び定理 2.3.4 から
 \not\equiv 1 \pmod{p}. このときフェルマーの小定理より
)^2 = a^{p-1} \equiv 1 \pmod{p}.
 \equiv -1 \equiv \left( \frac{a}{p} \right) \pmod{p}.
以上より定理は証明される。
証明 2
定理 1.8 より、A = \{ 0, a, 2a, \cdots , (p-1)a \} は剰余系をなすので、この中の任意の数 r について rs \equiv a \pmod{p} となる s \in A がただ一つ存在する。これを r の配偶と呼ぶことにする。
ここで \left( \frac{a}{p} \right) = 1 のとき r を x^2 \equiv a \pmod{p} の解とすれば、r の配偶はそれ自身である。また、
(p-r)^2 = p^2 - 2pr + r^2 \equiv r^2 \pmod{p} より p-r も方程式の解である。このとき r = p-r とすると p = 2r となり、奇素数であるという仮定に反する。したがって r \neq p-r.
合同方程式の基本定理から、上の方程式の解を満たすもの、すなわち配偶が自身であるものは r, p-r の2つであり、他の p-3 個の数は2個ずつ配偶があって、それらの積は
 \pmod{p}
であるから、
\begin{align}
 \\
 \\
 \pmod{p}. \\
\end{align}
 \pmod{p}
次に \left( \frac{a}{p} \right) = -1 のときは上の r, p-r のような数はないので配偶が \frac{p-1}{2} ペアできて
 \pmod{p}
a = 1 は自明に前に属すので (p-1)! \equiv -1 \pmod{p}（すなわちウィルソンの定理）。したがって、
 \equiv 1 \pmod{p}
 \equiv -1 \pmod{p}
これがオイラーの規準である。
p, q を相異なる奇素数としたときに
2, 3 をそれぞれ第一補充法則、第二補充法則という。まずはそれぞれの意味を説明する。
1 は、p, q のどちらかが 4n + 1 の形のとき \left( \frac{p}{q} \right) = \left( \frac{q}{p} \right) で、どちらとも 4n + 3 の形のときに限り \left( \frac{p}{q} \right) = - \left( \frac{q}{p} \right) である、という意味である。
2 は、x^2 \equiv -1 \pmod{p} に解がある \iff p \equiv 1 \pmod{4}
3 は、p = 8n + 1, \, 8n + 7 のとき \left( \frac{p}{q} \right) = 1 で、p = 8n + 3, \, 8n + 5 のとき \left( \frac{p}{q} \right) = -1 である。つまり x^2 \equiv 2 \pmod{p} に解がある \iff p \equiv 1, 7 \pmod{8}. 
証明
2 から証明する。
 \pmod{p}.
.
さて、3 であるが、これにはガウスの補題を用いる。
\gcd (a, p) = 1 のとき、A = \left\{ a, 2a, 3a, \cdots , \frac{p-1}{2} a \right\} をそれぞれ p で割ったときの余りが \frac{p}{2} より大きい数が n 個あったとき、
\left( \frac{a}{p} \right) = (-1)^n.
証明
ある数を p で割った余りが \frac{p}{2} よりも大きいならば、それから p を引くと -\frac{p}{2} よりも大きい負の余りを得る。つまり、絶対最小剰余である。上の n というのは負の絶対最小剰余の個数である。
A の任意の2つの数 ax, ay \ (x \neq y) について、
(a, p) = 1, \ \frac{1-p}{2} \leqq x \pm y \leqq \frac{p+1}{2} であり、x \pm y \neq 0 より、A の中には絶対最小剰余として等しいもの、また絶対最小剰余として符号が逆なものも存在しない。すなわち全体として符号を無視すれば
\left\{ 1, 2, 3, \cdots , \frac{p-1}{2} \right\} に合同で、そのうち負の数の個数が n である。したがって
a \cdot 2a \cdot 3a \cdots \frac{p-1}{2}a \equiv (-1)^n\cdot 1 \cdot 2 \cdot 3 \cdots \frac{p-1}{2}
だが、 1, 2, ..., \frac{p-1}{2} はいずれも p と互いに素なので
 \equiv (-1)^n
を得る。オイラーの規準によって
\left( \frac{a}{p} \right) \equiv (-1)^n \pmod{p}.
どちらも \pm 1 に等しく、p は奇素数なので
\left( \frac{a}{p} \right) = (-1)^n.
さて 3 の証明だが、
2, 4, 6, \cdots , p-1
の中で \frac{p}{2} より多いものの個数が n である。
(i) p = 8n + 1 のとき
\frac{p}{2} = 4n + \frac{1}{2}, \ p-1 = 8n なので、この間にある偶数の数は \frac{8n-4n}{2} = 2n であり、\left( \frac{2}{p} \right) = (-1)^{2n} = 1
 = 1 で、
.
(ii) p = 8n + 3 のとき
\frac{p}{2} = 4n + \frac{3}{2}, \ p-1 = 8n + 2 なので、この間にある偶数の数は \frac{(8n + 2) - (4n + 2)}{2} + 1 = 2n + 1 であり、\left( \frac{2}{p} \right) = (-1)^{2n + 1} = -1.
 = -1 で、
.
(iii) p = 8n + 5 のとき
\frac{p}{2} = 4n + \frac{5}{2}, \ p-1 = 8n + 4 なので、この間にある偶数の数は \frac{(8n+4) - (4n + 2)}{2} = 2n+1 であり、\left( \frac{2}{p} \right) = (-1)^{2n + 1} = -1.
 = -1 で、
.
(iv) p = 8n + 7 のとき
\frac{p}{2} = 4n + \frac{7}{2}, \ p-1 = 8n + 6 なので、この間にある偶数の数は \frac{(8n+4) - (4n + 4)}{2} = 2n であり、\left( \frac{2}{p} \right) = (-1)^{2n} = -1.
 = -1 で、
.
以上により 3 が証明される。
最後に相互法則であるが、初等整数論/平方剰余の相互法則の証明に譲る。
例 1 \left(\frac{31}{103}\right) を求めよ。
相互法則より
\left(\frac{31}{103}\right)=(-1)^{15\cdot 51} \left(\frac{103}{31}\right)=-\left(\frac{10}{31}\right)=-\left(\frac{2}{31}\right)\left(\frac{5}{31}\right)
となる。ここで、第二補充法則と相互法則を用いて
\left(\frac{2}{31}\right)=1, \left(\frac{5}{31}\right)=\left(\frac{31}{5}\right)=\left(\frac{1}{5}\right)=1
を得るから
\left(\frac{31}{103}\right)=-1
とわかる。
例 2 p が奇素数のとき
\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) =
\begin{cases} 1 (p\equiv 1, 4\pmod{5}), \\ -1 (p\equiv 2, 3\pmod{5}) \end{cases}
が成り立つ。