First Creation 2007/10/18
Last Update 2007/11/23
Bloody Mary > Column > 2007/10/18 - Thursday

合同式

≡ なんて記号、義務教育では出てこなかった気がする。

久しぶりに日記を更新したので手順を忘れてリンク張り忘れ・・・(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) ・・・ A

3. A を 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 日後の曜日は金曜日である。

ふと我に返る。あれ、オレ何やってんだ・・・? 強制された資格を取り終わって自由をもてあましている気がする。い、いかん。オレはもともと自由人のはずだ。こんなことしてないで遊べ。そういえば最近は釣りに行っていないなぁ。

前へ 上へ 通行止め