平方剰余と基本的な問題

$p=3$ のとき，

整数 $m$ を3で割った余りで分類する。

整数 $m$ は別の整数 $n$ を用いて $3n,3n+1,3n+2$ のいずれかの形で表せる。

$m\equiv 0\pmod{3}$ のとき $m^2\equiv 0\pmod{3}$

$m\equiv 1\pmod{3}$ のとき $m^2\equiv 1\pmod{3}$

$m\equiv 2\pmod{3}$ のとき $m^2\equiv 1\pmod{3}$

よって，$1$ は $3$ を法とする平方剰余だが $2$ は平方剰余ではない。

$p=4$ のときも同様に，整数 $m$ を4で割った余りで分類する。

$m\equiv 0\pmod{4}$ のとき $m^2\equiv 0\pmod{4}$

$m\equiv 1\pmod{4}$ のとき $m^2\equiv 1\pmod{4}$

$m\equiv 2\pmod{4}$ のとき $m^2\equiv 0\pmod{4}$

$m\equiv 3\pmod{4}$ のとき $m^2\equiv 1\pmod{4}$

よって，$1$ は $4$ を法とする平方剰余だが $2,3$ は平方剰余ではない。

背理法で証明する。 $a$ ，$b$ 両方奇数だと左辺を $4$ で割った余りは $2$ となるが，$4$ で割って $2$ 余る平方数は存在しないので矛盾。

背理法で証明する。 $a$ ，$b$ 両方 $3$ の倍数でないと左辺を $3$ で割った余りは $2$ となるが，$3$ で割って $2$ 余る平方数は存在しないので矛盾。