整数の基本3：剰余系（合同式）

はじめに

大詰めです．今回は整数の基本3ヶ条の3つ目，剰余系について解説していきます．（3ヶ条の記事を読んでいない場合はこちら(click!)から．）

「剰余」は，無限にある整数を有限個のグループに分けるための道具です．

今まで扱ってきた約数・倍数関係や大小関係は，直接的に「整数を絞り込む」方法でした．剰余はこれら2つとは異なり，間接的に絞り込んでいくことが多いです．

剰余系（合同式）の利用

「$m$による剰余系」とは，「$m$で割った余りで分類する」ということです．

約数・倍数関係は「割り切れる」ことに関するもので，剰余系は割り切れないものに関しても考えています．

剰余系はある意味では約数・倍数関係の拡張のようなものと言えるでしょう．

例えば$m=3$の場合，全ての整数は$\{3k,3k+1,3k+2\}$という3つの集合に分けられます．

大事なのは，この3つの集合で「全て」の整数が「被りなく一意に」分類出来ているという点なのですが，この辺には深く触れないでおきます．

例えばこのような問題の場合$n=\{3k,3k+1,3k+2\}$を代入することによって示すことができます．

「〜の倍数であることを示せ」という問題で剰余系が威力を発揮するのは当然と言えます．

合同式とは

さて，このように利用価値が高い「剰余」なのですが，「剰余」の計算を簡単にするための道具として「合同式」というものがあります．

「$a$と$b$を$m$で割った余りが等しい」ことを「$a$と$b$は$m$を法として合同」と呼びます．

そして，$a\equiv b(\text{mod}m)$と表記します．まさに三角形の合同で使った記号$\equiv$です．

modは法(modulo)のことで，「$m$で割った余りを考えていきますよ」という宣言だと思ってください．

さて，合同式にはいくつかの性質があります．大事なものを2つ紹介します．

1つめは「余り」の定義についてです．一般的に$m$で割った余りは$0$から$m-1$までの$m$種類です．

基本的に自然数に対してしか割り算や余りの計算をすることはなかったと思いますが，定義することは簡単です．

例えば$m=3$として，3で割って2余る数$x$を考えると，

$x\equiv 2\equiv 5\equiv 8\cdots$

と3を足していった形になりますが，当然引いていってもよく，

$x\equiv 2\equiv -1\equiv -4\cdots$

と書くことができます．負の余りを定義することで，合同式を用いた計算が楽になります．

「3で割った余りは$0,\pm 1$」のように，出来るだけ絶対値を小さく書くことが多いです．

一般化すると以下のような感じですね．

2つ目は，演算についてです．基本的に等式と同じように計算しても良い，ということですね．

が成立しています．

少し余談にはなりますが，この証明を考えてみましょう，

合同式は余りの計算．ですので，割り算の式を用いて表現できます．

「余りが等しい＝差が割り切れる」ですから，$a\equiv b(\text{mod}m)\iff a-b=km$を代入していけばすぐに示せます．

合同式を等式に直す式変形は非常に大事です．ぜひ覚えておきましょう．

特に積の部分が重要で，これを繰り返し用いることで，$a\equiv b\Rightarrow a^n\equiv b^n$が示せます．整数係数の整式が関わる問題で重要です．

（合同式の割り算は条件に制約があります．そもそも割りきれなかったら余りどうこうの問題ではなくなってしまいます．）

剰余系・合同式を用いた絞り込み

基本的な話はここまでです．はじめに「間接的に整数を絞り込む」と言いましたが，どのように使っていくのでしょう．

以下の例題を考えてみてください．

例題

2次方程式ですし，解の公式を使って解いてしまっても正答を出すことが出来ますが，今回は合同式を用いてみましょう．

$5p$が厄介ですね．これをどう扱うかが問題です．$p$は整数という条件しかありません．5で割り切れる数ですね．合同式を使うなら，法を5で取るべきでしょう．

「ない」ことを示す時は，背理法が便利です．二重否定で肯定的に扱っていきます．$x=\alpha$と置いて代入し，矛盾を導きましょう．

左辺は，${\alpha }^2+2\alpha -5p+2\equiv {\alpha }^2+2\alpha +2$で，右辺は0です．

いちいち$\alpha =5k,5k+1,5k+2\cdots$と代入していかなくても，合同式は和・差・積＋累乗に関して計算できますから，$\alpha \equiv 1$なら$f(\alpha )\equiv f(1)$が成立します．

$f(\alpha )=0$なのに$f(1)\not\equiv 0$であるところに矛盾が生じます．左辺が$\alpha =0,\pm 1,\pm 2$で0にならなければ，左辺と右辺が等しくならない，という論理ですね．

実は「矛盾を示す」のが，合同式の得意とするところなのです．

一般的に，等式「$=$」と合同式「$\equiv$」では，等式の方が強い条件です．

$a=b\Rightarrow a\equiv b$ですが，逆は成り立たない．

ですから，合同式から等式の条件を得るためには，対偶を考えて，$a\not\equiv b\Rightarrow a\ne b$とする必要があるのです．

というわけで，合同式を用いた絞り込みは．「一部の条件を除外する」イメージを持っておきましょう．

今回なら，$\alpha$から5で割って割り切れる数，1余る数，と順番に除外していった結果，何も残らなかった→整数解が存在しない，という風に解答を進めます．

例題解答

まとめ