合同式を利用したあまりの問題

今日の問題はこちら。

2000^{2000}

を

12

で割った余りを求めよ。

問題の意味は簡単ですね。累乗の意味がわかれば中学生でも理解できる問題です。

しかしながら、普通にやろうとしたら無理ですね。桁が大変なことになります（笑）。これをどう解くか。普通ならなんとかして”あまり”の周期性を調べていくやり方になると思います。それでもいいのですが、あまりの周期性をうまく表した数学の記法があります。

それは合同式です。おそらく通常の数学の課程では、発展的な内容ということでやらない人もいるのではないでしょうか。

しかし、これを知っていることで、あまり系の問題の見通しが良くなるので覚えておいて損はないです。さらに難関私立ではちょっと変わった問題が出題される傾向にあるので、色々なやり方を理解しておくことは周りの受験生に差をつけることに等しいです。

とりあえず合同式について簡単に説明します。この問題で使う知識しか用意しないので他の性質をみたい人は参考書へGO。

まず合同式とは何かと言うと

$a - b$ が $m$ の倍数であるとき、 $a$ 、 $b$ は $m$ を法として合同であるという。式で $a \equiv b (m o d m)$ と表し、これを合同式という。

です。これ本当にあまりに使えるの？と最初は疑問を感じると思いますが定義の式を変形すると少し見えてくるかもしれません。

$a - b = m k (k は定数) \leftarrow 定義 \Rightarrow a = b + m k$

左は定義式、右は $b$ を移項した式です。右の式にするとこれは

「 $a$ を $m$ で割った余りが $b$ である」

ということを表している式になっています。大丈夫ですね？あまりという言葉が出てきました。そうなんです。この式をみてわかる通り、”ある数字をある数字で割った余りが〇〇である”ということを一発で表しているのが合同式なんです。もう一度定義を載せておきます。

$a \equiv b (m o d m)$

イメージできたでしょうか。 $a$ を $m$ で割った余りが $b$ ですよ。

合同式についてイメージがついたところでこの合同式にはいくつかの性質がありますのでみていきましょう。普通の数字でいうと分配法則とか結合法則みたいなものですね。

私たちは普段全く意識しませんが、計算にはルールがあります。合同式ではどんなルールが出てくるのかを知らなければ計算はできません。国ごとに法律や憲法が違うのと同じです。新しく記法を定義したのならその計算方法（演算法）を確認しなければならないのです。

ここでは冒頭でも話した通り、問題に使う性質だけ説明します。

$\begin{matrix} a \equiv b (m o d m), c \equiv d (m o d m) \to a c \equiv b d (m o d m) \end{matrix}$

$\begin{matrix} a \equiv b (m o d m) \to a^{n} \equiv b^{n} (m o d m) \end{matrix}$

$\begin{matrix} a \equiv b (m o d m), b \equiv c (m o d m) \to a \equiv c (m o d m) \end{matrix}$

上の３つです。１つ目は、同じ $m$ が法な式のそれぞれの積も $m$ が法な合同式になることを表します。２つ目は両辺を $n$ 乗しても $m$ が法であることは変わらないということです。３つ目は３段論法の合同式バージョンです。

では早速問題に入りましょう。今回の問題は $2000^{2000}$ を $12$ で割った余りですが、いきなりこれをやったら合同式の意味がないので、まずは $2000$ と $12$ の関係を調べます。累乗部分は(4)式でなんとかなりそうです。

$2000$ を $12$ で割るとあまりは $8$ なので合同式を使って書くと

$2000 \equiv 8 (m o d 12)$

となります。OKですか？最終目標は $2000^{2000} \equiv ○ (m o d 12)$ となるような○の部分を探すことなので、式(3)と性質2より

$2000^{2000} \equiv 8^{2000} (m o d 12)$

です。もちろん「あまりは $8^{2000}$ です」なんて言っても”まだ割れるだろ！”と言われるだけなのでここをもっと小さくしなくてはなりません。ここで性質3を思い出すと次は

$8^{2000} \equiv ○ (m o d 12)$

となる丸の部分を探せば最終的に欲しい式までたどり着けそうです。要するに

$2000^{2000} \equiv 8^{2000} (m o d 12), 8^{2000} \equiv ○ (m o d 12) \to 2000^{2000} \equiv ○ (m o d 12)$

ということです。ここからモチベーションは $8^{2000} \equiv ○ (m o d 12)$ ですが、 $8^{2000}$ を $12$ で割るわけにも行かないので性質1,2をうまく使います。どういうことかというと

$8^{2} \equiv 4 (m o d 12)$

$8^{3} \equiv 8 (m o d 12)$

$8^{4} \equiv (8^{2})^{2} \equiv 4^{2} \equiv 4 (m o d 12)$

式(9)が大事で、２つ目の式変形は式(7)の結果から変形しています。イメージとしては代入ですね。

ここまでわかると $8^{2}$ と $8^{4}$ は同じあまりになっているのがわかりますし、最後の式変形をずっと繰り返せばもっと大きい累乗のものでも説明できるので

$8^{2 k} \equiv 4 (m o d 12)$

( $k$ は整数)であることを結論づけられます。 $8$ の偶数乗は $12$ で割るとあまりが $4$ であるということです。

ということは

$8^{2000} \equiv 4 (m o d 12)$

なので最終的に

$2000^{2000} \equiv 4 (m o d 12)$

なのであまりは $4$ になります。

いったん広告の時間です。

まとめ

どうだったでしょうか。合同式は発展的な内容ですので授業で取り扱う学校は少ないですが、整数の問題では使える場面があるので覚えておくと良いですよ。実は管理人も恥ずかしながら高校の時は合同式を知らなかったです（笑）。ぜひこの記事を読んでいる人には覚えて欲しいと思います。

ではまた。

いったん広告の時間です。

まとめ

コメント