まずこの補題を証明する。この補題は、平方剰余の相互法則だけではなく、いろいろな定理の補題としてよく使われる定理である。
補題1：\(p\)を素数とする。そのとき、\(n\)次合同方程式
\[f(x)\equiv 0 \pmod p \hspace{1cm}\cdots (1) \]は解をもってもその個数は\(n\)個以下である。
この証明に次の補題を使う。（補題の補題ってなんなんだ…。）
補題1.1:\(a\)と\(m\)が互いに素なとき、1次合同方程式
\[ax \equiv b \pmod m\]はただ1つの解を持つ。
証明:\(a\)と\(m\)が互いに素だから\(ax_{0}+my_{0}=1\)となる\(x_{0},y_{0} \in \mathbb{Z}\)がある。(この記事参照。)よって、
\[a\cdot bx_{0}-b=m\cdot (-by_{0})\]
したがって、\(x=bx_{0}\)は\(ax \equiv b \pmod m\)の解である。
\(x_{1},x_{2}\)を\(ax \equiv b \pmod m\)の2つの解とすると、\(ax_{1} \equiv ax_{2} \pmod m\)。
ここで、\(a\)と\(m\)が互いに素だから\(x_{1} \equiv x_{2} \pmod m\)となる。
補題1の証明
\(n\)に関する帰納法で示す。まず、
\[f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0}\]とすれば、\(p\)は\(a_{n}\)で割り切れないからである。\(n=1\)のときは、補題1.1より正しい。つぎに(1)が解\(x_{0}\)を持ったとする。このとき、
\[f(x)=(x-x_{0})g(x)+f(x_{0})\]ここで、\(g(x)\)は\(a_{n}x^{n-1}\)を最高次の項とする\(n-1\)次の整数係数の多項式を表す。したがって、(1)は次の合同方程式
\[(x-x_{0})g(x)\equiv 0 \pmod p\]と同一の解をもつ。そこで、(1)に\(x_{0}\)と異なる解がなければそれで補題は成立するので、\(x_{0}\)と異なる解\(x_{1}\)があったとする。そのとき、
\[(x-x_{0})g(x_{1})\equiv 0 \pmod p\]\(p \mid \hspace{-.67em}/ (x_{1}-x_{0})\)だから、。よって、\(g(x_{1})\equiv 0 \pmod p\)。つまり、\(x_{0}\)と異なる(1)の解は\(n-1\)次の合同方程式\(g(x)\equiv 0 \pmod p\)の解となる。ここで、帰納法の仮定を用い、(1)に高々\(n\)個の解しかないことがわかる。
