(Z/nZ)*の群構造

この記事では $(\mathbb{Z}/n\mathbb{Z})^{\times}$ の群構造についてまとめています。

1.1

$n=\prod_pp^{e_p}$ と素因数分解されているとき、中国剰余定理によって

$\displaystyle \mathbb{Z}/n\mathbb{Z} \simeq \prod_p\mathbb{Z}/p^{e_p}\mathbb{Z}$

が成り立つので、

$\displaystyle (\mathbb{Z}/n\mathbb{Z})^{\times} \simeq \prod_p(\mathbb{Z}/p^{e_p}\mathbb{Z})^{\times}$

を得る。すなわち、問題は $n=p^e$ のときに帰着される( $e_p$ は自然数)。

1.2

$e \geq 3$ のとき、 $5^{2^{e-3}} \not \equiv 1 \pmod{2^e}, \ \ 5^{2^{e-2}} \equiv 1 \pmod{2^e}$ が成り立つ。

証明. 奇数 $k_e$ が存在して、 $5^{2^{e-3}}=1+k_e2^{e-1}$ と書けることを示せばよい。 $e$ に関する帰納法で証明する。 $5=1+2^2$ なので、 $k_3=1$ 。 $k_e$ が存在したと仮定すると、

$5^{2^{e-2}} = (5^{2^{e-3}})^2=(1+k_e2^{e-1})^2=1+(k_e+k_e^22^{e-2})2^e$

より、 $k_{e+1}=k_e+k_e^22^{e-2}$ とすればよい(このとき $k_{e+1}$ は奇数)。 Q.E.D.

1.3

命題次の群の同型が成立する：

$(\mathbb{Z}/2^e\mathbb{Z})^{\times} \simeq \begin{cases} \text{単位群} & (e=1) \\ \mathbb{Z}/2\mathbb{Z} & (e=2) \\ \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{e-2}\mathbb{Z} & (e \geq 3) \end{cases}$

証明. $e=1, 2$ のときは明らか。 $e\geq 3$ 、 $G=(\mathbb{Z}/2^e\mathbb{Z})^{\times}$ とする。また、 $-1\bmod{2^e}$ (resp. $5\bmod{2^e}$ )が生成する $G$ の部分群を $\langle -1 \rangle$ (resp. $\langle 5 \rangle$ )と表す。 $4$ で割ったあまりを考えることによって、 $-1 \bmod{2^e} \not \in \langle 5 \rangle$ がわかるので、自然な埋め込み $\langle -1 \rangle \times \langle 5 \rangle \hookrightarrow G$ がある。1.2より

$\#(\langle -1 \rangle \times \langle 5 \rangle )= 2 \times 2^{e-2} = 2^{e-1} = \varphi (2^e) = \#G$

なので、

$(\mathbb{Z}/2^e\mathbb{Z})^{\times} \simeq \langle -1 \rangle \times \langle 5 \rangle \simeq \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{e-2}\mathbb{Z}$

が示された。 Q.E.D.

$\varphi (n)$ はEulerのトーシェント関数。 $\varphi (n) = \#(\mathbb{Z}/n\mathbb{Z})^{\times}$ である。

1.4

$p$ を素数とする。このとき、 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ は位数 $p-1$ の巡回群である。

これは原始根の存在からわかる：平方剰余の相互法則 - INTEGERS

1.5

$g$ を法 $p$ の原始根とする(1.4より存在する)。このとき、 $g$ または $g+p$ は $g^{p-1} \not \equiv 1 \pmod{p^2}$ を満たす。

証明. $(g+p)^{p-1} \equiv g^{p-1}+(p-1)g^{p-2}p \equiv g^{p-1}-g^{p-2}p \pmod{p^2}$
よりわかる。 Q.E.D.

$g$ を $g\not \equiv 1 \pmod{p^2}$ を満たすような法 $p$ の原始根とする。 $p$ が奇素数、 $e \geq 2$ ならば $g^{p^{e-2}(p-1)}=1+k_{e-1}p^{e-1}$ によって定義される $k_{e-1}$ は $p$ で割り切れないような整数である。

証明. $k_1$ が $p$ で割れないような整数であることは $g$ の取り方からOK。 $e \geq 3$ として数学的帰納法で証明する。すなわち、 $k_{e-2}$ は $p$ で割れない整数であると仮定する。このとき、

$\begin{equation}\begin{split}g^{p^{e-2}(p-1)}&=(1+k_{e-2}p^{e-2})^p \\ &= 1+k_{e-2}p^{e-1}+\sum_{j=2}^{p-1}\binom{p}{j}k_{e-2}^jp^{j(e-2)}+k_{e-2}^pp^{p(e-2)} \\ &\equiv 1+k_{e-2}p^{e-1} \pmod{p^e}\end{split}\end{equation}$

が成り立つ。ここで、pCrはpの倍数 - INTEGERS *1および $p > 2$ であることを用いている。従って、 $k_{e-1} \equiv k_{e-2} \pmod{p}$ であることがわかり、特に $k_{e-1}$ は $p$ で割れない整数である。 Q.E.D.

1.6

命題 $p$ を奇素数、 $e$ を自然数とする。このとき、 $(\mathbb{Z}/p^e\mathbb{Z})^{\times}$ は位数 $\varphi (p^e)=$ $p^{e-1}(p-1)$ の巡回群である。

証明. $g$ を $g \not \equiv 1 \pmod{p^2}$ なる法 $p$ の原始根とする。 $g$ の $(\mathbb{Z}/p^e\mathbb{Z})^{\times}$ における位数 $t$ は $p^{e-1}(p-1)$ の約数なので、非負整数 $a, b$ を用いて $t=p^ab$ と書ける( $a \leq e-1$ , $\ b \mid p-1$ )。 $b < p-1$ と仮定しよう。 $g^{t} \equiv 1 \pmod{p^e}$ なので、

$g^{p^ab} \equiv 1 \pmod{p}$

が成り立つが、Fermatの小定理によって

$g^b \equiv 1 \pod{p}$

となって $g$ が法 $p$ の原始根であることに反する。従って、 $t=p^a(p-1)$ を得る。すると、1.5より $a=e-1$ も従い、 $g$ が法 $p^e$ の原始根になっていることがわかった。 Q.E.D.

2.1

群の同型 $G \simeq H_1 \times H_2$ があって、 $H_1, H_2$ はそれぞれ位数 $n, m$ の巡回群とする。このとき、 $G$ が巡回群になるための必要十分条件は $n$ と $m$ が互いに素であることである。

証明. $G$ の任意の元 $g$ に対して $g^{\mathrm{lcm}(n, m)}=1$ が成り立つので、 $g$ の位数は $\mathrm{lcm}(n, m)$ を割り切る。従って、 $G$ が巡回群であれば $n$ と $m$ は互いに素でなければならない。逆は中国剰余定理よりわかる。 Q.E.D.