(Z/2^nZ)*の構造(オマケに高校数学風クイズ)

これは何?

金子晃先生の「応用代数講義」の命題4.26の証明がよくわからなかったし、わかったにしても構成が具体的でなくやっぱりよくわからないので、本の証明をヒントに自分でもうちょっと具体的な証明をつけなおしてみた。
最後にこれを考えてたらできた高校数学風クイズもあるよ!

示す命題

n≧3とし、 G=\mathbb{Z}_{2^n}^*とする。 G\simeq C_{2^{n-2}}\times C_2となる。
ここで、 G=\mathbb{Z}_{2^n}^* \mathbb{Z}/{2^n}\mathbb{Z}の乗法群である。

大事な観察

3の「2の羃」乗を2進法で表記すると、次のような法則が観察される:

  •  3 = \texttt{11} ←末尾の「1」と次の「1」との間に「0」は現れない
  •  3^{2^1} = 9 = \texttt{1001} ←末尾の「1」と次の「1」との間に「0」は2個あらわれる
  •  3^{2^2} =  (3^{2^1})^2 = 81 = \texttt{1010001} ←末尾の「1」と次の「1」との間に「0」は3個あらわれる
  •  3^{2^3} = (3^{2^2})^2 = 6561 = \texttt{1100110100001} ←末尾の「1」と次の「1」との間に「0」は4個あらわれる

そういうわけで、i≧1について、 3^{2^i}を2進法で表記したとき、末尾の「1」と次の「1」との間に「1」は i+1個あらわれるらしい。つまり、「1」が1つずつ左にずれていっているらしい。このことはあとでちゃんと示す。

したがって、 3, 3^{2^1}, 3^{2^2}, \dots, 3^{2^{n-3}}の2進法表記を下n桁(ただしn≧3)とったものを考えるとき、そのとったものたちはすべて相異なる。例えば、

  • n=3なら、  3 = \texttt{11}の2進法表記での下3桁は「001」で(1個しかないので当たり前だけど)相異なる。
  • n=4なら、 3 = \texttt{11}の2進法表記での下4桁は「0001」、 3^{2^1} = \texttt{1001}は「1001」でこの2つはやっぱり相異なる。
  • n=5なら、 3 = \texttt{11}の2進法表記での下5桁は「00001」、 3^{2^1} = \texttt{1001}は「01001」、 3^{2^2} = \texttt{1010001}は「10001」でこの3つはやっぱり相異なる。

となる。

証明

まず、Gは 2^n未満の奇数全体からなるので、位数は 2^{n-1}である。
「大事な観察」と、位数が2羃でありGの部分群の位数は2羃にならざるを得ない*1ことから3の位数*2はちょうど 2^{n-2}である。

ところで、 2^{n-1}-1 2^{n-1}+1との差は2なので、このうち少なくとも一方は3の倍数ではなく、したがって3の羃でもない。その3の羃でないほうをaとよぶことにする。aは(当然 2^nのmodをとって) a^2=1である。
 a\not\in \langle 3 \rangleであり、<3>の指数は2なので、G=<3>∪ a・<3>である。

群準同型 \varphi\colon C_{2^{n-2}}\times C_2 \to Gを、φ(0, 1)=a, φ(1, 0)=3で定める。これが同型であることを示そう。全射 \phi(x, y)=3^x \cdot yaとG=<3>∪ a・<3>より明らかである。
単射も<3>∩a・<3>=∅に注意すれば簡単である。これで同型が示された。

これでこういうクイズが作れますね

高校数学風に、こういう問題が作れますね(多分うまく誘導作れば本当に高校数学の問題になるんですけど)。

431をn(正の自然数)乗して1024で割った余りを計算すると1になったという。そのようなnのうち最小のものを求めよ。ただし、431は511×81を1024で割った余りである。

答えは上の事実を使えばもちろん簡単で、511は512=1024/2から1を引いたものでかつ3の倍数でないので、上の証明で言うところのaとして選べる。さらに81のほうは3の4乗である。
よって、上の同型で431∈ \mathbb{Z}_{1024}^*(=G)を飛ばすと、(φの逆をψと書くことにして)ψ(431)=(4,1)∈ C_{256}\times C_2となる。
Gの方でn回羃をとることは、 C_{256}\times C_2では両方の要素にn倍することに相当するので、n×(4,1)=(0, 0)となる最小のnを考えればよく、これは明らかに256/4=64である。よって答えは64。

*1:ラグランジュの定理

*2:3の羃の生成する巡回部分群の位数