部分群とラグランジュの定理

前のステージの終わりで、要素の位数（くり返して初めて単位元になる回数）が、いつも群の個数の約数になっていた。今日はその理由を証明する。これが分かると、mod p（p で割った余りで考える世界）の累乗について、フェルマーの小定理という強い道具が手に入る。次のステージの暗号の心臓部になる定理だ。まず、群の中の小さな群を考えよう。正三角形の6つの操作のうち、回転だけを集めた e, r, r² を調べてごらん。

そう。群 G の一部分で、同じ計算でそれだけで群になっているものを、G の部分群という。e, r, r² は正三角形の群の部分群だ。部分群を調べるのは、大きな群を、小さな群の組み合わせとして理解するためだよ。整数を素因数に分けて調べるのに似ているね。では、e と s₁ の2つは部分群かな？ e と r の2つはどうかな？

そう。mod 12 の足し算の群でも探してみよう。0 から 11 を「足して 12 で割った余り」で計算する群だったね。集まりを { } でくくって書くことにしよう。H＝{0, 4, 8} は部分群かな？

そう。では、H＝{0, 4, 8} の全部に 1 を足してみよう。2 を足したら？ 3 を足したら？

そう。部分群 H を「ずらしたコピー」で、群全体がきれいに等分割されたね。H の全部の要素の前に同じ g をつけた集まりを、H の剰余類（じょうよるい）という。積で書く群なら gH＝{gh（h は H の要素）}、つまり「g をしてから、H のどれかをする」操作の集まりだ。足し算の群なら g＋H と書く。正三角形の群で、H＝{e, s₁} の剰余類を全部作ってごらん。

そう。どんな群でも、どんな部分群でも、こうなる。それを3つの段階で確かめよう。1つ目。剰余類 gH の要素の個数は、いつも H と同じかな？

そう。2つ目。群のどの要素 g も、どこかの剰余類に入っているかな？

そう。3つ目がいちばん大事だ。2つの剰余類 gH と kH が1つでも共通の要素をもったら、2つはまったく同じ集まりになる。これを確かめよう。共通の要素を x とすると、x＝gh＝kh′ と書ける。h と h′ は H の要素だ。

その通り。まとめると、剰余類はどれも H と同じ個数で、群の全部をおおい、1つでも重なるなら丸ごと一致する。だから群全体は、H と同じ個数の組に、重ならずにぴったり分かれる。

そう。これをラグランジュの定理という。ラグランジュは1770年ごろ、方程式の解の入れ替えを研究するなかで、この定理のもとになる事実を見つけた。だから彼の名前で呼ばれている。では、前のステージの謎に戻ろう。群の個数が有限なら、a, a², a³, … と掛けていくと、いつか同じものが出てくる。aⁱ＝a^j（i＜j）となったら、両辺の前に a⁻¹ を i 回すれば a^j−i＝e。だから、くり返せばいつか必ず e になり、位数が決まる。a の位数が k なら、e, a, a², …, a^k−1 の k 個は、どんな集まりになるかな？

そう。群の個数を m とすると、m は k で割り切れる。すると a^m はどうなるかな？

そう。これを、mod p の掛け算の群（p は素数）にあてはめてごらん。

それがフェルマーの小定理だ。1640年、フェルマーは友人への手紙にこの事実を書いた。証明は書かなかったけれど、群の考え方を使うと、いまのように数行で示せる。使い道を1つ見てみよう。3¹⁰⁰ を 7 で割った余りは？

そう。巨大な累乗の余りも、指数を p−1 で割った余りまで縮められる。次のステージでは、素数でない n についても同じことを考え、それを鍵にした暗号を作ろう。