時計の算術

この章の最後に15パズルを解くときも、STAGE5 で暗号を作るときも、「何回かくり返すと、もとに戻る」計算が要る。いちばん身近な例は時計だ。いま 9 時だとして、5 時間後は何時かな？

そう。時計の 12 時を 0 と読みかえると、時刻は 0 から 11 の 12 個で、足し算は「足してから 12 で割った余りをとる」ことになる。2つの整数 a と b を n で割った余りが等しいとき、a ≡ b (mod n) と書いて、「mod n で a と b は合同」と読む。mod は、ラテン語で「尺度」を意味する modulus（モジュラス）を略した言葉だ。たとえば 14 ≡ 2 (mod 12) だ。そして、余りだけで計算する世界を「mod n の世界」と呼ぼう。

そう。その言いかえは便利だから覚えておこう。では、余りだけで計算してよい理由を確かめよう。a を n で割った余りが r、b を n で割った余りが r′ のとき、a＋b や ab を n で割った余りは、r と r′ だけで決まるかな？

その通り。たとえば、100×100 を 7 で割った余りを、10000 を割らずに求めてごらん。

そう。では、mod n の足し算が群になっているか確かめよう。集まりは 0, 1, …, n−1 の n 個、計算は「足して n で割った余り」だ。群の4つの条件は、閉じている・結合法則・単位元・逆元だったね。

そう。これを「mod n の足し算の群」と呼ぼう。数が n 個ある群だ。では掛け算はどうか。0 を掛けるといつも 0 になって、もとに戻せない。だから 0 を除いた 1 から n−1 で考える。mod 7 と mod 6 で掛け算表を作って比べてごらん。

そう。mod 6 では、0 でない数どうしを掛けても 0 になることがあるから、1 から 5 の中で閉じていないし、2 には逆元もない。群にならないんだ。では、mod 7 ではなぜいつもうまくいくのか。7 が素数であることが効いてくる。p を素数として、1 から p−1 のある数 a の行を考えよう。その行に同じ数が2回出たとする。つまり、1 から p−1 の異なる x, y（x＞y とする）で a×x ≡ a×y (mod p) になったとする。

そう。素因数分解がただ1通りであることは、中学校から使ってきたね。なぜただ1通りなのかは、第2章でじっくり調べる。これで、a の行に同じ数が2回出ないことが分かった。それから、a×x が 0 になることもないね。

その通り。だから、p が素数なら、mod p の 1 から p−1 は掛け算で群になる。単位元は 1 だ。これを「mod p の掛け算の群」と呼ぼう。数が p−1 個ある群だね。

そう。次は、1つの数をくり返し掛けていこう。mod 7 で、3, 3², 3³, … を順に計算してごらん。

そう。群の要素 a をくり返し掛けて、はじめて単位元になる回数を、a の位数（いすう）という。mod 7 の掛け算の群で、3 の位数は 6 だ。では 2 はどうかな？

その通り。3 のように、くり返し掛けるだけで群の要素を全部作れる要素を生成元という。そして、1つの生成元の累乗で全部が書ける群を巡回群と呼ぶ。くるくる回って全部を巡るからだ。mod 7 の掛け算の群は、3 を生成元とする巡回群なんだ。

そう。では、正三角形の6つの操作の群全体は、巡回群かな？

そう。巡回群では a^maⁿ＝a^m＋n＝aⁿa^m だから、いつでも順番を入れかえられる。順番で結果が変わる正三角形の群は、その点からも巡回群ではないと分かるね。最後に、ここまでに出てきた位数を並べてみよう。mod 7 の掛け算の群は 6 個の数からなり、位数は 1, 2, 3, 6 のどれかになる。正三角形の群も 6 個で、位数は 1, 2, 3 だ。どちらも、位数が群の個数 6 の約数になっている。

そう。これは偶然ではない。次のステージで、その理由を証明する。そこから、暗号のもとになる「フェルマーの小定理」が出てくるんだ。