 |
 |
 |
 |
| First Creation | 2007/10/18 |
|---|---|
| Last Update | 2007/11/23 |
合同式
≡ なんて記号、義務教育では出てこなかった気がする。
久しぶりに日記を更新したので手順を忘れてリンク張り忘れ・・・(2007/10/30 リンク)
数学の勉強
友人から「2007/01/01 が月曜日だったとして、17^16 日後は何曜日か分かる？」と質問されたので、解き方をググって見ると、合同式というのを見つけたが、慣れない表記を理解するまで結構時間がかかった。
ちなみに、 17^16 は 17 の 16 乗のこと。
この問題を解く考え方としてはこうだ。
前提条件
1/1 が 月曜日なら 7 日後の 1/8 も月曜日になる。8 日後の 1/9 は火曜日だ。以降同様に、 9 日後は水曜日、 10 日後は木曜日となる。当たり前なことを言っている。何のひねりもない。
曜日は 7 日ごとに 1 巡するので、 曜日を求めるには 7 で割った余りを求めればよい。つまり、 7 日後ならあまりは 0 なので月曜日、8 日後ならあまりは 1 なので火曜日といった具合に。これを表に表すとこうなる。
| 7 で割ったあまり | 曜日 |
|---|---|
| 0 | 月曜日 |
| 1 | 火曜日 |
| 2 | 水曜日 |
| 3 | 木曜日 |
| 4 | 金曜日 |
| 5 | 土曜日 |
| 6 | 日曜日 |
ここまでは知識ではなく知恵の範囲である。
力技なら、 2000 桁まで扱えるフリーの電卓ソフト「Q's cals」あたりを使って 17^16 を計算し、 7 で割った余りを出せばいい。
17^16 - INT(17^16/7) * 7 = 4
つまり、金曜日だ。
計算機用の関数を使うなんて邪道だという話であれば、Windows の関数電卓を使って、
17^16 = 48,661,191,875,666,868,481 ( 4866 京っておぃ・・・ )
6,951,598,839,380,981,211 * 7 = 48,661,191,875,666,868,477 となって、面倒だから末尾 3 桁で計算すると 481 - 477 = 4 だからあまりが 4 となる。当然上記の答えと同じで金曜日となるわけだ。
問題はこれを手動でやろうとした場合である。あまりを求めるのにうってつけの式がある。合同式という。暗号解読に必要となる初級の知識らしい。
合同式
a - b が m で割り切れるとき、 a と b は m を法として合同であるといい、次の式で表される。
a ≡ b (mod m)
たとえば、 17 ≡ 3 (mod 7) であれば、17 - 3 = 14 となり、 7 で割り切れる。
21 ≡ 3 (mod 6) も、 21 - 3 = 18 となり、 6 で割り切れる。
どちらの式も、 3 が余りになるわけだ。
さらにこの合同式というやつは、 ≡ が ＝ に似ているだけあって、次のような定理が成り立つ。
a ≡ b (mod m)
c ≡ d (mod m)
のとき、
1. a + c ≡ b + d (mod m)
2. a * c ≡ b * d (mod m)
3. a ^ n ≡ b ^ n (mod m)
1 を変形して、 a ≡ b + d - c (mod m) なんてのも OK。性質も ＝ に似ているようだ。これも例にしてみると分かりやすい。
1. a + c ≡ b + d (mod m)
たとえば
17 ≡ 3 (mod 7)
22 ≡ 1 (mod 7)
のとき、
17 + 22 ≡ 3 + 1 (mod 7)
39 ≡ 4 (mod 7)
( 7 * 5 = 35 だから、 39 を 7 で割るとあまりが 4 でる )
2. a * c ≡ b * d (mod m)
同様に掛け算も、
17 * 22 ≡ 3 * 1 (mod 7)
374 ≡ 3 (mod 7)
( 7 * 53 = 371 で、あまりが 3 になる )
3. a ^ n ≡ b ^ n (mod m)
掛け算が成り立つならべき乗算も OK なわけで
17 * 17 ≡ 3 * 3 (mod 7)
( 17^2 ≡ 3^2 (mod 7) と表される)
289 ≡ 9 (mod 7)
( 7 * 40 = 280 。 7 で割った余りが 9 というのも微妙な話だが・・・このように、表現できないわけではない )
上記は 2 乗の計算だが、
| 17 ≡ 3 (mod 7) | |
| × | 17 ≡ 3 (mod 7) |
| × | 17 ≡ 3 (mod 7) |
| × | 17 ≡ 3 (mod 7) |
| × | 17 ≡ 3 (mod 7) |
| ---------------- | |
| 17^5 ≡ 3^5 (mod 7) | |
となり、 n 乗が求められる。
a ≡ b + d - c (mod m)
1 の変形だって
17 ≡ 3 + 1 - 22 (mod 7)
17 ≡ - 18 (mod 7)
負の数があまりというのは理解が難しいが、合同式は a - b が m で割り切れるときに a ≡ b (mod m) と表せると言うだけあって、 17 - (-18) = 35 となって 7 で割り切れるから、この式も正しいと言うことが分かる。
17 - 35 = -18 で、 17 を 7 で割ると -18 あまると考えれば納得しやすいか。
数学というのは現実と乖離しているところがあるから、そういうのは体で覚えるようにしておけば、いずれ納得できたと錯覚できる日が来るだろう。
計算開始
さて、いよいよ計算してみる。17^16 後を求めるので、まずは a ≡ b (mod m) で、 a = 17, m = 7 の合同式を作る。
1. 17 を 7 で割る合同式を作る。
17 ≡ 3 (mod 7) ・・・ ①
2. ①を 2 乗してみる
17^2 ≡ 3^2 ≡ 9 ≡ 2 (mod 7)
この合同式を初めて見たとき、理解できなかった。
17^2 ≡ 3^2 (mod 7) になるのは分かるのである。
そこから右辺に展開された式が何故 2 (mod 7) になるのかが分からなかった。
答えは単純だった。9 ≡ 2 (mod 7) にだけ注目すればよかったのだ。ここは別の式？なのだ。 9 を 7 で割ると 2 あまる。それだけの話だった。分かってしまえばあとは数をこなせばいいだけである。その前に整理。
17^2 ≡ 2 (mod 7) ・・・ ②
3. ② を 8 乗すると、(17^2)^8 = 17^16 となるから
17^16 ≡ 2^8 ≡ 256 ≡ 4 (mod 7)
( 7 * 36 = 252 になる )
つまり、17^16 を 7 で割ったときのあまりは 4 になるわけで、前提条件に当てはめると金曜日に相当する。
結論：1/1 が月曜日のとき、 17^16 日後の曜日は金曜日である。
ふと我に返る。あれ、オレ何やってんだ・・・？ 強制された資格を取り終わって自由をもてあましている気がする。い、いかん。オレはもともと自由人のはずだ。こんなことしてないで遊べ。そういえば最近は釣りに行っていないなぁ。
