Z/nZの単元群の構造の話
こんにちは,ぱいです.
月に1回ぐらいはブログ更新したいなーと思っていて,前に記事を書いてから1か月ぐらい経ちました.
最近ゼミで $(\mathbb{Z}/n\mathbb{Z})^{\times}$ の群構造の勉強をしたので,そのことを書いていきます.
$n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{t}^{a_{t}}$ と因数分解されているとき中国剰余定理により
\begin{eqnarray}\mathbb{Z}/n\mathbb{Z}\cong(\mathbb{Z}/p_{1}^{a_{1}}\mathbb{Z})\times(\mathbb{Z}/p_{2}^{a_{2}}\mathbb{Z})\times\dots\times(\mathbb{Z}/p_{t}^{a_{t}}\mathbb{Z})\end{eqnarray}
という環の同型があるので,単元群について次のような同型が成り立ちます;
\begin{eqnarray}(\mathbb{Z}/n\mathbb{Z})^{\times}\cong(\mathbb{Z}/p_{1}^{a_{1}}\mathbb{Z})^{\times}\times(\mathbb{Z}/p_{2}^{a_{2}}\mathbb{Z})^{\times}\times\dots\times(\mathbb{Z}/p_{t}^{a_{t}}\mathbb{Z})^{\times}\end{eqnarray}
よって,$(\mathbb{Z}/n\mathbb{Z})^{\times}$ の群構造を考えるには,素数 $p$ で $(\mathbb{Z}/p^{a}\mathbb{Z})^{\times}$ の構造を調べれば十分です.
まずは,シンプルな $(\mathbb{Z}/p\mathbb{Z})^{\times}$ を考えてみましょう.
そのために,いくつか準備をしておきます.
命題1.(フェルマーの小定理) $p\nmid a$ なら $a^{p-1}\equiv1\bmod p$ が成り立つ.
(証明)
$a$ に関する帰納法で $a^{p}\equiv a\bmod p$ が示せる.$■$
命題2.$k$ が体で $f(x)\in k[x]$ の次数が $n$ なら,$f$ の $A$ における根は高々 $n$ 個しかない.
(証明)
$n$ に関する帰納法で,因数定理を用いて示せる.$■$
系3.$d\mid p-1$ なら $x^{d}\equiv1\bmod p$ は丁度 $d$ 個の解を持つ.
(証明)
命題2より,$x^{d}-1\equiv0$ は高々 $d$ 個の解をもつ.
そこで,$x^{d}-1\equiv0$ の解が $d$ 個よりも少ないと仮定する.
さて,$p-1=de$ とおくと
\begin{eqnarray}x^{p-1}-1&=&(x^{d})^{e}-1\\&=&(x^{d}-1) ( (x^{d})^{e-1}+(x^{d})^{e-2}+\dots+x^{d}+1)\end{eqnarray}
なので,この根の個数は $d+d(e-1)$ 個よりも少ない.つまり $p-2$ 個以下のはずである.
ところが,フェルマーの小定理より $x^{p-1}-1$ は $1,2,\dots,p-1$ の $p-1$ 個の根をもつ.
これは矛盾しているので,$x^{d}-1$ の根は丁度 $d$ 個である.$■$
定理4. $p$ が素数なら $(\mathbb{Z}/p\mathbb{Z})^{\times}$ は巡回群となる.
(証明)
$(\mathbb{Z}/p\mathbb{Z})^{\times}$ の位数は $p-1$ なので,位数 $p-1$ の元の存在を示せばいい.
$p-1=q_{1}^{a_{1}}q_{2}^{a_{2}}\dots q_{t}^{a_{t}}$ と因数分解しておき,各 $i$ について次の2つの方程式を考える;
\begin{eqnarray}x^{q_{i}^{a_{i}-1}}&\equiv&0\bmod p\hspace{15pt}(1)\\ x^{q_{i}^{a_{i}}}&\equiv&0\bmod p\hspace{15pt}(2)\end{eqnarray}
系3から,(2)の方が(1)よりもたくさんの解をもつ.
そこで各 $i$ について,(1)をみたさないが(2)をみたすようなものを $g_{i}$ とおく.
すると,各 $i$ で $g_{i}$ の$\bmod p$ での位数は $q_{i}^{a_{i}}$ である.
実際,$g_{i}$ は(2)の解だから位数は $q_{i}^{b_{i}}\ (b\leq a_{i})$ という形をしているが,もし $b_{i}\lneq a_{i}$と仮定すると
\begin{eqnarray}g_{i}^{q_{i}^{a_{i}-1}}&=&(g_{i}^{q_{i}^{b_{i}}})^{q_{i}^{a_{i}-1-b}}\\&\equiv&1\hspace{30pt}\bmod p\end{eqnarray}
となり,これは $g_{i}$ が(1)をみたさないことに矛盾する.
よって $b_{i}=a_{i}$ である.
さて,$g:=g_{1}g_{2}\dots g_{t}$ とおく.
すると,$g$ の位数が $p-1$ であることが次のようにしてわかる.
まず,各 $i$ で $q_{i}^{a_{i}}\mid p-1$ より $g_{i}^{p-1}\equiv 1$ なので $g^{p-}$ となる.
よって,$g$ の位数を $n$ とおくと $n$ は $p-1$ の倍数で,$n=q_{1}^{c_{1}}q_{2}^{c_{2}}\dots q_{t}^{c_{t}}\ (c_{i}\leq a_{i})$ という形をしている.
ある $k$ で $c_{k}\lneq a_{k}$ となると仮定し,$m:=q_{1}^{a_{1}}q_{2}^{a_{2}}\dots q_{k}^{c_{k}}\dots q_{t}^{a_{t}}$ とおく.($q_{k}$ の肩だけ $c$ で,他の肩は $a$)
すると,$i\neq k$ で $q_{i}^{a_{i}}\mid m $ で $i=k$ で $q_{k}^{a_{k}}\not\mid m $ なので
\begin{eqnarray}g^{m}&\equiv&g_{k}^{m}\\&\not\equiv&1\bmod p\end{eqnarray}
である.
ところが $m $ は $n$ の倍数なので $g^{m}\equiv 1\bmod p$ であり,これは矛盾している.
したがってすべての $i$ で $c_{i}=a_{i}$ で,$n=p-1$ となる.
つまり,この $g$ が $(\mathbb{Z}/p\mathbb{Z})$ の生成元である. $■$
定義5. $(\mathbb{Z}/n\mathbb{Z})^{\times}$ が巡回群のとき,その生成元を$\bmod p$ に対する原始根と呼ぶ.
定理4は,$p$ が素数なら$\bmod p$ に対する原始根が存在するということを言っていたのでした.
それでは, $(\mathbb{Z}/p^{l}\mathbb{Z})^{\times}$ を見ていきましょう.
そのために,いくつかの補題を用意しておきます.
補題6. $a\equiv b\bmod p^{l}$ なら $a^{p}\equiv b^{p}\bmod p^{l+1}$ となる.$(l\geq1)$
(証明)
$a\equiv b\bmod p^{l}$ のとき,ある $c\in\mathbb{Z}$ で $a=b+cp^{l}$ と表せるので,
\begin{eqnarray}\displaystyle a^{p}&=&(b+cp^{l})^{p}\\&=&b^{p} + pb^{p-1}cp^{l+1} + \sum_{k=2}^{p} {}_{p}\mathrm{C}_{k} b^{p-k}c^{k}p^{kl}\\&\equiv&b^{p}\bmod p^{l+1}\end{eqnarray}
となる. $■$
系7. $l\geq 2$,$p\neq 2$ のとき,$ (1+ap)^{p^{l-2}}\equiv 1+ap^{l- 1}\bmod p^{l}$ となる.$(\forall a\in\mathbb{Z})$
(証明)
$l$ の帰納法で示す.
$l=2$ のときはオッケー.
$l$ で主張が正しいと仮定すると,この仮定に補題6を用いて
\begin{eqnarray}( (1+ap)^{p^{l-2}})^p\equiv (1+ap^{l - 1})^{p}\bmod p^{l}\end{eqnarray}
つまり
\begin{eqnarray}\displaystyle (1+ap)^{p^{l- 1}}&\equiv&1+pap^{l- 1}+ \sum_{k=2}^{p-1}{}_{p}\mathrm{C}_{k}a^{k}p^{k(l- 1)} + a^{p}p^{p(l- 1)}\\&\equiv&1+ap^{l}\bmod p^{l+1}\end{eqnarray}
を得る. $■$
系8. $l\geq 2$,$p\neq 2$ で $p\not\mid a$ のとき,$1+ap$ の$\bmod p^{l}$ での位数は $p^{l- 1}$ である.
(証明)
$l+1$ で系7を用い,$(1+ap)^{p^{l- 1}}\equiv 1\bmod p^{l}$ がわかる.
また,系7より $(1+ap)^{p^{l-2}}\not\equiv 1\bmod p^{l}$ である.
よって,定理4の証明のときと同じような方法で $1+ap$ の$\bmod p^{l}$ での位数は $p^{l- 1}$ と分かる. $■$
さて,この補題を使って $(\mathbb{Z}/p^{l}\mathbb{Z})^{\times}$ の構造を調べていくのですが,$p=2$ のとき例えば $l=3,\ a=3$ とかでこの補題は成立しません.
だから,$p$ が奇素数のときと $p=2$ のときとで分けて考えていきます.
定理9. $p$ が奇素数のとき,$(\mathbb{Z}/p^{l}\mathbb{Z})^{\times}$ は巡回群である.
(証明)
まず,$\bmod p$ の原始根 $g$ で $g^{p-1}\not\equiv 1\bmod p^{2}$ となるものがとれることを示す.
定理4より$\mod p$ の原始根 $g$ はとれる.
この $g$ で $g^{p-1}\equiv 1\bmod p^{2}$ となるときは,代わりに $g+p$ をとればいい.
実際,このとき $g+p$ も$\bmod p$ の原始根だし,
\begin{eqnarray}\displaystyle (g+p)^{p1}&=&g^{p-1} + (p-1)g^{p-2}p + \sum_{k=2}^{p-1}{}_{p-1}\mathrm{C}_{k}g^{p-1-k}p^{k}\\&\equiv&1+(p-1)g^{p-2}p\bmod p^{2}\\ &\not\equiv& 1\bmod p^{2}\end{eqnarray}
である.
よって,$g^{p-1}\not\equiv 1\bmod p^{2}$ なる$\bmod p$ の原始根 $g$ がとれる.
さて,この $g$ が$\bmod p^{l}$ の原始根となることを示す.
今 $(\mathbb{Z}/p^{l}\mathbb{Z})$ の位数はオイラー関数を用いて $\phi(p^{l})=p^{l- 1}(p-1)$ なので,
\begin{eqnarray} g^{n}\equiv 1\bmod p^{l}\Rightarrow p^{l- 1}(p-1)\mid n\end{eqnarray}
を示せばよい.
さて,$g^{n}\equiv 1\bmod p^{l}$ のとき $g^{n}\equiv 1\bmod p$ で,$g$ は$\bmod p$ で位数 $p-1$ だから,$p-1\mid n$ を得る.
また,$g$ の選び方から,$g^{p-1}$ は $p$ と互いに素なある $a\in\mathbb{Z}$ を用いて $g^{p-1}=1+ap$ と表せる.
このとき
\begin{eqnarray}(1+ap)^{n}&=&(g^{p-1})^{n}\\&=&(g^{n})^{p-1}\\&\equiv&1\bmod p^{l}\end{eqnarray}
で,系8より $1+ap$ の$\bmod p^{l}$ での位数は $p^{l- 1}$ なので,$p^{l- 1}\mid n$ を得る.
今,$p-1$ と $p^{l- 1}$ は互いに素だから,以上から $p^{l- 1}(p-1)\mid n$ となる. $■$
さて,$\bmod n$ の原始根は必ずしも存在するとは限りません.
例えば, $(\mathbb{Z}/8\mathbb{Z})^{\times}=\{1,3,5,7\}$ は位数 $4$ の元を持たず巡回群でないので,$\bmod 8$ の原始根は存在しません.
$(\mathbb{Z}/2\mathbb{Z})^{\times}=\{1\}$ と $(\mathbb{Z}/4\mathbb{Z})^{\times}=\{1,3\}$ は巡回群ですが,$l\geq 3$ に対して $(\mathbb{Z}/2^{l}\mathbb{Z})^{\times}$ は違った構造になっています.
補題10. $l\geq 3$ に対して,$5$ の$\bmod 2^{l}$ での位数は $2^{l-2}$ である.
(証明)
まず,$5^{2^{l-3}}\equiv 1+2^{l- 1}\bmod 2^{l}$ を $l$の帰納法で示しておく.
$l=3$ のときは明らかにオッケー.
$l$ で主張が正しいと仮定すると,この仮定に補題6を用いて
\begin{eqnarray}(5^{2^{l-3}})^{2}\equiv (1+2^{l- 1})^{2} \bmod 2^{l+1}\end{eqnarray}
つまり
\begin{eqnarray}5^{2^{l-2}}&\equiv&1+2^{l}+2^{2(l- 1)}\\&\equiv&1+2^{l}\bmod 2^{l}\end{eqnarray}
である.従って,すべての $l\geq 3$で
\begin{eqnarray}5^{2^{l-3}}&\equiv&1+2^{l- 1}\bmod 2^{l}\\&\not\equiv&1\bmod2^{l}\end{eqnarray}
である.また,$5^{2^{l-2}}\equiv 1+2^{l}\bmod 2^{l+1}$ より $5^{2^{l-2}}\equiv 1\bmod 2^{l}$ である.
よって,定理4の証明のときと同じ方法で,$5$ の$\bmod 2^{l}$ での位数は $2^{l-2}$ とわかる. $■$
定理11. $l\geq 3$ に対して $(\mathbb{Z}/2^{l}\mathbb{Z})^{\times}$ は$C_{2}\times C_{2^{l-2}}$ と同型.ただし $C_{r}$ は位数 $r$ の巡回群.
(証明)
$G:=\left\{\overline{(-1)^{a}5^{b}}\mid a=0,1,\ 0\leq b<2^{l-2}\right\}$ とおく.ただし $\overline{x}$ は $x$ の$\bmod 2^{l}$ での剰余類とする.
まず,$\overline{(-1)^{a}5^{b}}$ たちがそれぞれ異なることを示す.
$(-1)^{a}5^{b}\equiv (-1)^{c}5^{d}\bmod 2^{l}$ のとき,$5\equiv 1\bmod 4$ より $(-1)^{a}1^{b}\equiv(-1)^{c}1^{d}\bmod 4$ つまり $(-1)^{a}\equiv(-1)^{c}\bmod 4$ となる.
よって $a=c$ となる.
このとき $5^{b}\equiv 5^{d}\bmod 2^{l}$ より $5^{b-d}\equiv 1\bmod 2^{l}$ である.
よって補題10より $b-d$ は $2^{l-2}$ の倍数なので,$0\leq b,d<2^{l-2}$ より $b=d$ となる.
従って $G$ の元の個数は $2^{l- 1}=\phi(2^{l})$ なので,$(\mathbb{Z}/2^{l}\mathbb{Z})=G$ となる.
よって $(\mathbb{Z}/2^{l}\mathbb{Z})\cong C_{2}\times C_{2^{l-2}}$ である. $■$
以上をまとめると,$(\mathbb{Z}/n\mathbb{Z})^{\times}$ の構造は次のようになります.
定理12.$n=2^{a}p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{t}^{a_{t}}$ と因数分解されているとき,
\begin{eqnarray}(\mathbb{Z}/n\mathbb{Z})\cong (\mathbb{Z}/2^{a}\mathbb{Z})^{\times}\times C_{\phi(p_{1}^{a_{1}})}\times C_{\phi(p_{2}^{a_{2}})}\times\dots\times C_{\phi(p_{t}^{a_{t}})}\end{eqnarray}
であり,$(\mathbb{Z}/2^{a}\mathbb{Z})^{\times}$ は $a=1,2$ のときそれぞれ $C_{1},C_{2}$ と同型で,$a\geq 3$ のとき $C_{2}\times C_{2^{a-2}}$ と同型である.
ではまた.
(途中,まちがいを指摘してもらって書き直しました.2017.6.12)
参考文献
Ireland, Kenneth; Rosen, Michael. 1990. A Classical Introduction to Modern Number Theory. New York: Springer-Verlag.