2014/04/27

平方剰余と基本的な問題

分野: 整数問題  レベル: 入試対策

平方数に関する重要な性質:
1:平方数を3で割った余りは必ず0か1。余りが2になることはない。
2:平方数を4で割った余りは必ず0か1。余りが2か3になることはない。

平方剰余の意味と具体例

$m^2\equiv a\:\mathrm{mod}\:p$ となる整数 $m$ が存在するとき,$a$ は $p$ を法とする平方剰余であるといいます。
平方剰余の考え方は整数問題で非常に重要で,特に $p=3,4$ が頻出です。
($\:\mathrm{mod}\:p$ の意味がよく分からない人は合同式の意味とよく使う6つの性質を参照してください。)

平方剰余のイメージをつかむために上記の性質1,2を証明してみます。

$p=3$ のとき,
整数 $m$ を3で割った余りで分類する。
整数 $m$ は別の整数 $n$ を用いて $3n,3n+1,3n+2$ のいずれかの形で表せる。
$m\equiv 0\:\mathrm{mod}\:3$ のとき $m^2\equiv 0\:\mathrm{mod}\:3$
$m\equiv 1\:\mathrm{mod}\:3$ のとき $m^2\equiv 1\:\mathrm{mod}\:3$
$m\equiv 2\:\mathrm{mod}\:3$ のとき $m^2\equiv 1\:\mathrm{mod}\:3$
よって,$1$ は $3$ を法とする平方剰余だが $2$ は平方剰余ではない。

$p=4$ のときも同様に,整数 $m$ を4で割った余りで分類する。
$m\equiv 0\:\mathrm{mod}\:4$ のとき $m^2\equiv 0\:\mathrm{mod}\:4$
$m\equiv 1\:\mathrm{mod}\:4$ のとき $m^2\equiv 1\:\mathrm{mod}\:4$
$m\equiv 2\:\mathrm{mod}\:4$ のとき $m^2\equiv 0\:\mathrm{mod}\:4$
$m\equiv 3\:\mathrm{mod}\:4$ のとき $m^2\equiv 1\:\mathrm{mod}\:4$
よって,$1$ は $4$ を法とする平方剰余だが $2,3$ は平方剰余ではない。

平方剰余の嬉しさ

・後で見るように,平方剰余の考え方は不定方程式の問題で答えの範囲を絞るのに使えます。入試問題でも数学オリンピックでも重要な考え方です。

・オイラーの規準,平方剰余の相互法則など便利な公式が整備されています。これらの公式は数学オリンピックなどの難問でたまに威力を発揮します。
→ルジャンドル記号とオイラーの規準
→平方剰余の相互法則の意味と応用

・入試問題では $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$ 余る平方数は存在しないので矛盾。

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

Tag: 不定方程式の解き方まとめ

分野: 整数問題  レベル: 入試対策