平方剰余と基本的な問題

更新日時 2021/03/07

平方剰余とは

「平方数を $p$ で割った余りが $a$ になる場合がある」とき， $a$ は法 $p$ で平方剰余であると言う。

平方剰余は「平方数を割り算したときの余り」に関する用語です。平方剰余について詳しく解説します。

平方剰余の例

例として，法 $p$ が $3$ である場合の平方剰余について考えます。平方数を3で割った余りがどうなるか？という話題です。

例

補足：

平方剰余の定義を合同式を使って表すと以下のようになります。

平方剰余の定義（合同式を使った表現）

$m^2\equiv a \pmod{p}$ となる整数 $m$ が存在するとき， $a$ は $p$ を法とする平方剰余であるといいます。

法が3と4の場合の平方剰余に関して，以下の性質が成り立ちます。

平方数に関する重要な性質

法が3の場合はさきほど確認しました。法が4の場合も確認してみます。

平方数を4で割った余り

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

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

このように， $p$ で割った余りで分類することで，法 $p$ の平方剰余を列挙できます。

平方剰余の考え方は不定方程式の問題で答えの範囲を絞るのに使えます。入試問題でも数学オリンピックでも重要な考え方です。特に $p=3$ または $4$ とするとうまくいく場合が多いです。

例題1

不定方程式 $a^2+b^2=c^2$ の整数解において， $a$ と $b$ のどちらか一方は偶数であることを証明せよ。

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

$4$ を法とする平方剰余の考え方を用いています。不定方程式の解の範囲を絞ることができています。ちなみに，この例題1を発展させることで全てのピタゴラス数を求めることができます。 →ピタゴラス数の求め方とその証明

例題2

不定方程式 $a^2+b^2+3ab=c^2$ の整数解において， $a$ と $b$ のどちらか一方は $3$ の倍数であることを証明せよ。

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

平方剰余に限らず，余りによる分類は整数問題の最強の道具の1つです。