数IAIIB高校数学の解法

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

合同式習ったけど,公式がなんで成り立つのか分かりません。

文字使うとわかんなくなるから,なるべく具体的な例で考えてみようか。

ad

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

合同式の公式
$a\equiv c\space(\bmod\space m)$,$b\equiv d\space(\bmod\space m)$ のとき
$a+b\equiv c+d\space(\bmod\space m)$
$a-b\equiv c-d\space(\bmod\space m)$
$ab\equiv cd\space(\bmod\space m)$
$a^k\equiv c^k\space(\bmod\space m)$

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

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

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

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

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

こんな感じで,1周回ってもとに戻るポイントをって言う。時計の長針は値を 60 で割った余りを表している。

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

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

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

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

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

ad

合同式の和と差

合同式では 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 分を指しているのと同じことです。

$-57$ って余り $3$?

$-57=60\times(-1)+3$ って表せるから,60 で割って余り $3$ とする。高校数学では余りは負の数にしないってのが一応ルール。

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

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

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

$5-2\equiv5-2$

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

ad

合同式の積

公式③ $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$ と表すこともできます。

とにかく $\bmod\space60$ なら,値から 60 のかたまりを取り除いて考える。それが合同式。

累乗

公式④ $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$

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

公式③でやった感じで,たとえば $62^5\equiv182^5$ は 60 のかたまり取り除いて $2^5\equiv2^5$ って考えても同じことなの。

演習問題

自然数 $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)$ とする。

右辺が 1 になるように,左辺を設定するのがポイント。

なんで,右辺は 1 なんですか?

1 は何乗しても 1 であることを利用したいから。

上で紹介した公式 $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 つの解き方を比べてみると,結局やっていることはほとんど同じです。ただ,合同式を使った方が式がシンプルに書けます。

結局,合同式って使うべき?使わないべき?

人によっていろいろ。ある程度練習積んでて使いこなせる自信があるなら使えばいいし,自信なければ使わない。あと,大学によって使わないところはまったく使わないから,志望校の過去問を確認して決めると良い。

タイトルとURLをコピーしました