解答例 1

すべての整数は, それぞれ $p$ を法として $0$, $1$, $\ldots$, $p-1$ のいずれかに合同である. また, 任意の整数 $a$, $b$ に対して, $$ a\equiv b\!\!\!\pmod{p} \Longrightarrow a^{2}\equiv b^{2}\!\!\!\pmod{p} $$ が成り立つ. ゆえに, すべての平方数は, それぞれ $p$ を法として $$ \begin{array}{lllll} 0^{2}, & 1^{2}, & 2^{2}, & \ldots, & (p-1)^{2} \end{array} $$ のいずれかに合同である. 一方, 任意の整数 $a$ に対して, $$ (p-a)^{2}\equiv a^{2}\pmod{p} $$ が成り立つ. このことから, \begin{align*} (p-1)^{2} &\equiv 1^{2}\pmod{p}, \\ (p-2)^{2} &\equiv 2^{2}\pmod{p}, \\ & \cdots\cdots, \\ \left(\frac{p+1}{2}\right)^{2} & = \left(p-\frac{p-1}{2}\right)^{2} \equiv\left(\frac{p-1}{2}\right)^{2}\pmod{p}. \end{align*} したがって, すべての平方数は, それぞれ $p$ を法として ($*$) のいずれかに合同である.

$a$, $b$ を整数とすると, \begin{align*} a^{2}\equiv b^{2}\!\!\!\pmod{p} & \Longrightarrow (a+b)(a-b)=a^{2}-b^{2}\equiv 0\!\!\!\pmod{p} \\ & \Longrightarrow \mbox{$a+b\equiv 0\!\!\!\pmod{p}$ または $a-b\equiv 0\!\!\!\pmod{p}$}. \end{align*} さらに, $0\leq a\leq (p-1)/2$, $0\leq b\leq (p-1)/2$, $a\neq b$ ならば, $a-b\not\equiv 0\pmod{p}$ であり, また, $$ 0 < a+b < \frac{p-1}{2} + \frac{p-1}{2} = p-1 $$ であるから, $a+b\not\equiv 0\pmod{p}$. ゆえに, ($*$) はどの2つも $p$ を法として互いに合同ではない.

最終更新日：2011年11月02日