ホーム >> 整数 >> 合同式の基礎・基本

整数問題 (特に剰余に関わる問題) で絶大な威力を発揮する合同式の基礎事項について解説します.




合同式とはなにか

整数問題の中でも特によく出題されるのが剰余に関わる問題です.剰余とは余りのことで,たとえば,『$2^{40}$ を $7$ で割った余りを求めよ.』などのように余りを問う問題がよくあります.また,不定方程式の整数解を求める際にも,剰余の考え方を用いることで,解を絞れることがあります.

整数そのものより,むしろその整数の余り (剰余) の方に関心がある場合は合同式を用いると便利です.簡単に言えば,整数全体をある数で割った余りで分類し,余りが同じ整数はすべて同じ (合同) とみなすのです.

合同式の記号

合同記号の記述方法を説明します.

整数 $a$ と $b$ を 整数 $m$ で割った余りが等しいとき,$a$ と $b$ は $m$ を法として合同といい, $$a \equiv b   (mod\ m)$$ とかく.

$a$ と $b$ を三本線で結び,何で割った余りなのかわかるように,式の右側に ($mod$〜) とかくのが慣習です.

$mod\ m$ の $mod$ というのは $modulo$ の略です.

$\underline{Example}$
・$4 \equiv 2 (mod\ 2)$
・$13 \equiv 1 (mod\ 3)$
・$8 \equiv 0 (mod\ 4)$
・$5 \equiv -1 (mod\ 6)$
・$1234 \equiv 2 (mod\ 7)$

整数 $a$ と $b$ を 整数 $m$ で割った余りが等しいというのは,$a-b$ が $m$ の倍数ということと同値です.こちらの言い方のほうがわかりやすいかもしれません.一番最後の例を見るとわかるように,どれほど大きな数でも余りに関しては割る数より小さくできます.これが剰余を考えることのメリットです.

合同式の基本的な性質

合同式に関して次の基本的性質が成り立ちます.

$a \equiv b,\ c \equiv d$ のとき,次が成り立つ.ただし,すべて $m$ に関する法で考えているものとする.

($1$) $a+c \equiv b+d$
($2$) $a-c \equiv b-d$
($3$) $ac \equiv bd$
($4$) $a^n \equiv b^n$ ($n$ は自然数)

要するに,加法,減法,乗法を行っても合同を保ちます.よく使うのが ($4$) です.後の例題でその使い方を解説します.ところで,注意すべきことは,除法では,一般に合同を保たないということです.たとえば, $$12 \equiv 24 (mod 6)$$ ですが,両辺を $4$ で割って, $$3 \equiv 6 (mod 6)$$ などとすることはできません.実際,$3$ と $6$ は $6$ を法として合同ではありません.一般に,除法に関しては次のことが成り立ちます.

$ac \equiv bc (mod\ m)$ のとき,$c$ と $m$ が互いに素ならば,$a \equiv b (mod\ m)$ が成り立つ.

つまり,割る数と法が互いに素でないと,除法が安心して行えません.

例題

$2^{40}$ を $7$ で割った余りを求めよ.

$2^{40}$ を計算してから筆算で $7$ で割った余りを求めるのは面倒です.基本的なアイデアは,$40$ 乗という指数部分を計算する前に,合同式で $2^{40}$ を簡単にしてしまおうということです.

$2^3=8 \equiv 1 (mod\ 7)$ です.ここで,自然数 $n$ に対して, $$(2^3)^n \equiv 1^n=1$$ です.$2^{40}=2\times (2^3)^{13}$ なので, $$2^{40}=2\times (2^3)^{13} \equiv 2\times 1=2 (mod\ 7) $$ よって,$2^{40}$ を $7$ で割った余りは $2$.

この問題では, $2^3$ を $7$ で割った余りが $1$ となったので,簡単に余りを求めることができました.このように,与えられた式の一部が合同式の意味で $1$ や $-1$ や $0$ などの簡単な数になってくれれば,その式がかなり簡単になるので,簡単になる部分を探すというのがポイントになります.もう一つ簡単な例題を見てみましょう.

$5^{2016}$ を $13$ で割った余りを求めよ.

決して $5^{2016}$ を計算しようとしないでください.計算する必要はないのです.まず,$5^{2016}$ の部分のうち,$13$ で割って簡単になる部分を探します.すると,$5^2=25 \equiv -1 (mod\ 13)$ ということに気づきます.ここがポイントです.

$5^2=25 \equiv -1 (mod\ 13)$ です.したがって, $$5^{2016}=(5^2)^{1013} \equiv (-1)^{1013}=-1 \equiv 12 (mod\ 13)$$ よって,$5^{2016}$ を $13$ で割った余りは $12$.

このように,負の数を利用すると,計算が簡単になります.基本的には,$1,0,-1$ などと合同な部分を探して,与えられた数を丸め込んでやるとうまくいくことが多いです.


まだまだ合同式に関しては多くの重要な事実があるので,徐々にステップアップしていきましょう.