合同式の基礎・基本|思考力を鍛える数学

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

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

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

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

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

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

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

・$4 \equiv 2 (\rm{mod}\ 2)$ ・$13 \equiv 1 (\rm{mod}\ 3)$ ・$8 \equiv 0 (\rm{mod}\ 4)$ ・$5 \equiv -1 (\rm{mod}\ 6)$

・$1234 \equiv 2 (\rm{mod}\ 7)$

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

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

$m$ を整数とする.$a \equiv b,\ c \equiv d~~~(\rm{mod}\ m)$ のとき,次が成り立つ. ($1$) $a+c \equiv b+d~~~(\rm{mod}\ m)$ ($2$) $a-c \equiv b-d~~~(\rm{mod}\ m)$ ($3$) $ac \equiv bd~~~(\rm{mod}\ m)$ ($4$) $a^n \equiv b^n~~~(\rm{mod}\ m)$ ($n$ は自然数)

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

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

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

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

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

$2^3=8 \equiv 1~~~(\rm{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~~~(\rm{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~~~(\rm{mod}\ 13)$ ということに気づきます.ここがポイントです.

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

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

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

Copied title and URL