structure of ${(\mathbb{Z}/n\mathbb{Z})}^{\times }$ as an abelian group

The automorphism group of the cyclic group $C_n\cong \mathbb{Z}/n\mathbb{Z}$ is ${(\mathbb{Z}/n\mathbb{Z})}^{\times }$. This article determines the structure of ${(\mathbb{Z}/n\mathbb{Z})}^{\times }$ as an abelian group.

Theorem 1.

Let $n\mathrm{\ge }\mathrm{2}$ be an integer whose factorization is $n\mathrm{=}{p}_{\mathrm{1}}^{a_{\mathrm{1}}}\mathit{}{p}_{\mathrm{2}}^{a_{\mathrm{2}}}\mathit{}\mathrm{\dots }\mathit{}{p}_r^{a_r}$ where the $p_i$ are distinct primes. Then:

1. ${(\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 \mathrm{\dots }\times {(\mathbb{Z}/p_r^{a_r}\mathbb{Z})}^{\times }$

2. ${(\mathbb{Z}/p^k\mathbb{Z})}^{\times }$ is a cyclic group of order $p^{k-1}(p-1)$ for all odd primes $p$.

3. ${(\mathbb{Z}/2^k\mathbb{Z})}^{\times }$ is the direct product of a cyclic group of order $2$ and a cyclic group of order $2^{k-2}$ for $k\ge 2$.

Corollary 2.

$\mathrm{Aut}(C_n)\cong {(\mathbb{Z}/n\mathbb{Z})}^{\times }$ is cyclic if and only if $n\mathrm{=}\mathrm{2}\mathrm{,}\mathrm{4}\mathrm{,}{p}^k$, or $\mathrm{2}\mathit{}{p}^k$ for $p$ an odd prime and $k\mathrm{\ge }\mathrm{0}$ an integer.

Proof.

(of theorem)
(1): This is a restatement of the Chinese Remainder Theorem.

(2): Note first that the result is clear for $k=1$, since then ${(\mathbb{Z}/p\mathbb{Z})}^{\times }$ is the multiplicative group of the finite field $\mathbb{Z}/p\mathbb{Z}$ and thus is cyclic (any finite subgroup of the multiplicative group of a field is cyclic). Also, $\left|{(\mathbb{Z}/p^k\mathbb{Z})}^{\times }\right|=\varphi (p^k)=p^{k-1}(p-1)$. Since ${(\mathbb{Z}/p^k\mathbb{Z})}^{\times }$ is abelian, it is the direct product of its $q$-primary components for each prime $q\mid \varphi (p^k)$; we will show that each of those $q$-primary components is cyclic. For $q=p$, it suffices to find an element of ${(\mathbb{Z}/p^k\mathbb{Z})}^{\times }$ of order $p^{k-1}$. $1+p$ is such an element; see Lemma 3 below. For $q\ne p$, consider the map

$$\mathbb{Z}/p^k\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}:a+(p^k)\mapsto a+(p)$$

i.e. the reduction-by-$p$ map. This is a ring homomorphism; restricting it to ${(\mathbb{Z}/p^k\mathbb{Z})}^{\times }$ gives a surjective group homomorphism $\pi :{(\mathbb{Z}/p^k\mathbb{Z})}^{\times }\to {(\mathbb{Z}/p\mathbb{Z})}^{\times }$. Since $\left|{(\mathbb{Z}/p\mathbb{Z})}^{\times }\right|=p-1$, it follows that the kernel of $\pi$ has order $p^{k-1}$. Thus for $q\ne p$, the $q$-primary component of ${(\mathbb{Z}/p^k\mathbb{Z})}^{\times }$ must map isomorphically into ${(\mathbb{Z}/p\mathbb{Z})}^{\times }$ by order considerations. But ${(\mathbb{Z}/p\mathbb{Z})}^{\times }$ is cyclic, so the $q$-primary component is as well.

Thus each $q$-primary component of ${(\mathbb{Z}/p^k\mathbb{Z})}^{\times }$ is cyclic and thus ${(\mathbb{Z}/p^k\mathbb{Z})}^{\times }$ is also cyclic.

(3): The result is true for $k=2$, when ${(\mathbb{Z}/2^2\mathbb{Z})}^{\times }\cong V_4$, the Klein $4$-group. So assume $k\ge 3$. $5$ has exact order $2^{k-2}$ in ${(\mathbb{Z}/2^k\mathbb{Z})}^{\times }$ (see Lemma 4 below). Also by that lemma, $5^{2^{k-3}}\ne -1$ is ${(\mathbb{Z}/2^k\mathbb{Z})}^{\times }$, so that $5^{2^{k-3}}$ and $-1$ are two distinct elements of order $2$. Thus ${(\mathbb{Z}/2^k\mathbb{Z})}^{\times }$ is not cyclic, but has a cyclic subgroup of order $2^{k-2}$; the result follows.∎

Proof.

(of Corollary)
$(\Leftarrow )$ is clear, since

$(\Rightarrow )$: Assume ${(\mathbb{Z}/n\mathbb{Z})}^{\times }$ is cyclic. If $n$ is a power of $2$, then by the theorem, it must be either $2$ or $4$. Otherwise, if $n$ has two distinct odd prime factors $p,q$, then ${(\mathbb{Z}/n\mathbb{Z})}^{\times }$ contains the direct product ${(\mathbb{Z}/p^r\mathbb{Z})}^{\times }\times {(\mathbb{Z}/q^s\mathbb{Z})}^{\times }$. But the orders of these two factor groups are both even (they are $\varphi (p^r)=p^{r-1}(p-1)$ and $\varphi (q^s)=q^{s-1}(q-1)$ respectively), so their direct product is not cyclic. Thus $n$ can have at most one odd prime as a factor, so that $n=2^m{p}^k$ for some integers $m,k$, and

$${(\mathbb{Z}/C_n\mathbb{Z})}^{\times }={(\mathbb{Z}/C_{2^m}\mathbb{Z})}^{\times }\times {(\mathbb{Z}/C_{p^k}\mathbb{Z})}^{\times }$$

But the order of ${(\mathbb{Z}/C_{p^k}\mathbb{Z})}^{\times }$ is even, so that (since the order of ${(\mathbb{Z}/C_{2^m}\mathbb{Z})}^{\times }$ is also even for $m\ge 2$) we must have $m=0$ or $1$, so that $n=p^k$ or $2p^k$.

∎

The above proof used the following lemmas, which we now prove:

Lemma 3.

Let $p$ be an odd prime and $k\mathrm{>}\mathrm{0}$ a positive integer. Then $\mathrm{1}\mathrm{+}p$ has exact order $p^{k\mathrm{-}\mathrm{1}}$ in the multiplicative group ${\mathrm{(}\mathrm{Z}\mathrm{/}{p}^k\mathit{}\mathrm{Z}\mathrm{)}}^{\mathrm{\times }}$.

Proof.

The result is obvious for $k=1$, so we assume $k\ge 2$. By the binomial theorem,

$${(1+p)}^{p^n}=1+\sum _{i=1}^{p^n}\left(\genfrac{}{}{0pt}{}{p^n}{i}\right)p^i$$

Write ${\mathrm{ord}}_p(m)$ for the largest power of a prime $p$ dividing $m$. Then by a theorem on divisibility of prime-power binomial coefficients,

$${\mathrm{ord}}_p\left(\left(\genfrac{}{}{0pt}{}{p^n}{i}\right)p^i\right)=n+i-{\mathrm{ord}}_p(i)$$

Now, $i-{\mathrm{ord}}_p(i)$ is $1$ if $i=1$, and is at least $2$ for $i>1$ (since $p\ge 3$). We thus get

$${(1+p)}^{p^n}=1+p^{n+1}+r{p}^{n+2},r\in \mathbb{Z}$$

Setting $n=k-1$ gives ${(1+p)}^{p^{k-1}}\equiv 1(p^k)$; setting $n=k-2$ gives ${(1+p)}^{p^{k-2}}\equiv 1+p^{k-1}\not\equiv 1(p^k)$.∎

Lemma 4.

For $k\mathrm{\ge }\mathrm{3}$, $\mathrm{5}$ has exact order ${\mathrm{2}}^{k\mathrm{-}\mathrm{2}}$ in the multiplicative group ${\mathrm{(}\mathrm{Z}\mathrm{/}{\mathrm{2}}^k\mathit{}\mathrm{Z}\mathrm{)}}^{\mathrm{\times }}$ (which has order ${\mathrm{2}}^{k\mathrm{-}\mathrm{1}}$). Additionally, ${\mathrm{5}}^{{\mathrm{2}}^{k\mathrm{-}\mathrm{3}}}\mathrm{\not\equiv }\mathrm{-}\mathrm{1}\mathrm{(}{\mathrm{2}}^k\mathrm{)}$.

Proof.

The proof of this lemma is essentially identical to the proof of the preceding lemma.Again by the binomial theorem,

$$5^{2^n}={(1+2^2)}^{2^n}=\sum _{i=1}^{2^n}\left(\genfrac{}{}{0pt}{}{2^n}{i}\right)2^{2i}$$

Then

$${\mathrm{ord}}_2\left(\left(\genfrac{}{}{0pt}{}{2^n}{i}\right)2^i\right)=n+2i-{\mathrm{ord}}_2(i)$$

Now, $2i-{\mathrm{ord}}_2(i)$ is $2$ if $i=1$, and is at least $3$ for $i>1$. We thus get

$$5^{2^n}=1+2^{n+2}+r{2}^{n+3},r\in \mathbb{Z}$$

Setting $n=k-2$ gives $5^{2^{k-2}}\equiv 1(2^k)$; setting $n=k-3$ gives $5^{2^{k-3}}\equiv 1+2^{k-1}\not\equiv \pm 1(2^k)$. (Note that $1+2^{k-1}\not\equiv -1$ since $k\ge 3$).∎