【数IA整数】合同式は時計のイメージで理解する：入試問題での使い方

時計で分かる合同式と法のイメージ

合同式とは，余りの部分だけを取り出すと左右イコールであることを示したものです。

$a\equiv b\space(\bmod\space m)$

このとき，$a$ と $b$ は $m$ を法として合同であると言います。

時計で説明すると分かりやすいでしょう。

たとえば，時計の針を 0 分をスタート地点としてぐるぐると回していったとき，5 分と 125分では時計の長針は同じところを指します。このとき5 と 125 は 60 を法として合同であると言うことができるのです。

これを合同式として表すと

$5\equiv125\space(\bmod\space60)$

となります。右辺を書き換えると

$5\equiv60\times2+5\space(\bmod\space60)$

125 のうち，60で割り切れる部分を取り除いて，残りの部分だけで考えるのが合同式です。時計で言えば，針が何周回ったかは無視して長針の位置だけで考えるということです。

合同式の和と差

合同式では 4 つの公式を学びます。一つずつ見ていきましょう。

$a\equiv c\space(\bmod\space m)$，$b\equiv d\space(\bmod\space m)$ のとき

公式①　$a+b\equiv c+d\space(\bmod\space m)$

時計の長針で考えてみましょう。たとえば長針は 5 分と 65 分ではいずれも 5 分のところを指し，62 分と 182 分はいずれも 2 分のところを指します。よって

$5\equiv65\space(\bmod\space60)$

$62\equiv182\space(\bmod\space60)$

と表すことができます。そして，左辺と右辺をそれぞれ足し合わせた

$5+62\equiv65+182\space(\bmod\space60)$
$67\equiv247\space(\bmod\space60)$

が成り立ちます。つまり，時計の針が何周回ったか考えずに，長針の位置だけを考え，5 分の位置から 2 分進んで 7 分の位置に移動したということです。

同じように引き算も成り立ちます。

公式②　$a-b\equiv c-d\space(\bmod\space m)$

$5-62\equiv65-182\space(\bmod\space60)$
$-57\equiv-117\space(\bmod\space60)$

はじめに時計の針を 0 分の位置に合わせ，そこから 57 分戻したら 3 分の位置を指します。117 分戻す場合も同様です。これは長針だけで考えれば，5 分の位置から 2 分戻して 3 分を指しているのと同じことです。

結局のところ，60 を法とする合同式では，60 のかたまりを取り除いた部分だけで考えるので

$5-62\equiv65-182\space(\bmod\space60)$

から 60 のかたまりを取り除いて

$5-2\equiv5-2$

として考えても同じことです。

合同式の積

公式③　$ab\equiv cd\space(\bmod\space m)$

さきほどの例で考えてみましょう。

$5\equiv65\space(\bmod\space60)$

$62\equiv182\space(\bmod\space60)$

のとき

$5\times62\equiv65\times182\space(\bmod\space60)$

が成り立ちます。式は

$5\times(60+2)\equiv(60+5)\times(60\times3+2)$
$5\times60+5\times2\equiv60^2\times3+60\times2+60\times5\times3+5\times2$

両辺から 60 のかたまりを取り除くと $5\times2$ だけが残ります。

このように考えることもできます。

$5\times62\equiv65\times182\space(\bmod\space60)$

結局 60 の積になる部分がいらないのだから，はじめから 60 のかたまりを取り除けばよいのです。

$5\times62\equiv65\times182\space(\bmod\space60)$
$5\times2\equiv5\times2\space(\bmod\space60)$

上の 2 つの式は同じことを表していて，$5\times62\equiv5\times2$ としたり，$65\times182\equiv5\times2$ と表すこともできます。

累乗

公式④　$a^k\equiv c^k\space(\bmod\space m)$

この公式は公式③ $ab\equiv cd$ から求めることができます。$b$ ⇒ $a$，$d$ ⇒ $c$ とすれば

$a\times a\equiv c\times c$

が成り立つので

$a\times a\times\cdots\times a\equiv c\times c\times\cdots\times c$
$a^k\equiv c^k$

としても，ちゃんと合同が成り立ちます。

演習問題

自然数 $m$ は，2 進法で 101 が 6 回連続する表示

$101101101101101101_{(2)}$

をもつとする。$m$ を 7 で割った余りを求めよ。（九州大2018文系・改）

---

まず，合同式を使わずに解いてみます。

$101_{(2)}$ は 10 進法になおすと，5 です。よって

$m=101101101101101101_{(2)}$
$=5\cdot2^{15}+5\cdot2^{12}+5\cdot2^9+5\cdot2^6+5\cdot2^3+5\cdot2^0$
$=5(2^{15}+2^{12}+2^9+2^6+2^3+1)$

$2^3=8$ だから

$=5(8^5+8^4+8^3+8^2+8^1+1)$
$=5\{(1+7)^5+(1+7)^4+(1+7)^3+(1+7)^2+1+7+1\}$

二項定理を用いて

$=5\{(1+_5C_11^4\cdot7^1+\cdots+7^5)+(1+_4C_11^3\cdot7^1+\cdots+7^4)+(1+_3C_11^2\cdot7^1+\cdots+7^3)+(1+2\cdot1\cdot7+7^2)+7+2)\}$

ここで，7 の倍数を $7k$ とすると

$=5(7k+1+1+1+1+2)$

と表すことができる。

$=5(7k+6)$
$=35k+30$
$=7(5k+4)+2$

したがって，$m$ を 7 で割った余りは 2。（答え）

合同式を使った場合

$8\equiv1\space(\bmod\space7)$ とする。

上で紹介した公式 $a^k\equiv c^k$ を用いると

$8^k\equiv 1^k\equiv1\space(\bmod\space7)$

これは，8 を何乗してもその数を 7 で割ると余りは 1 であるということを意味します。

$m=101101101101101101_{(2)}$
$=5(8^5+8^4+8^3+8^2+8^1+8^0)$

ここで

$5(8^5+8^4+8^3+8^2+8^1+8^0)\equiv5(1+1+1+1+1+1)\space(\bmod\space7)$

よって

$m\equiv5\cdot6\equiv30\space(\bmod\space7)$

ここで，右辺から 7 のかたまりを取り除くと

$m\equiv2\space(\bmod\space7)$

が成り立ちます。したがって，$m$ を 7 で割った余りは 2。（答え）

2 つの解き方を比べてみると，結局やっていることはほとんど同じです。ただ，合同式を使った方が式がシンプルに書けます。