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

###### Theorem 1.

Let $n\geq 2$ be an integer whose factorization is $n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{r}^{a_{r}}$ where the $p_{i}$ are distinct primes. Then:

1. 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\dots% \times(\mathbb{Z}/{p_{r}^{a_{r}}}\mathbb{Z})^{\times}$

2. 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. 3.

$(\mathbb{Z}/{2^{k}}\mathbb{Z})^{\times}$$2$ and a cyclic group of order $2^{k-2}$ for $k\geq 2$.

###### Corollary 2.

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

###### Proof.

(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\lvert(\mathbb{Z}/{p^{k}}\mathbb{Z})^{\times}\right\rvert=\phi(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\phi(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\neq 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\lvert(\mathbb{Z}/{p}\mathbb{Z})^{\times}\right\rvert=p-1$, it follows that the kernel of $\pi$ has order $p^{k-1}$. Thus for $q\neq 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\geq 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}}\neq-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

 $\begin{array}[]{ll}(\mathbb{Z}/{C_{2}}\mathbb{Z})^{\times}\cong\{1\}&\quad(% \mathbb{Z}/{C_{4}}\mathbb{Z})^{\times}\cong C_{2}\\ (\mathbb{Z}/{C_{p^{k}}}\mathbb{Z})^{\times}\cong C_{p^{k-1}(p-1)}&\quad(% \mathbb{Z}/{C_{2p^{k}}}\mathbb{Z})^{\times}\cong(\mathbb{Z}/{C_{2}}\mathbb{Z})% ^{\times}\times(\mathbb{Z}/{C_{p^{k}}}\mathbb{Z})^{\times}\cong C_{p^{k-1}(p-1% )}\end{array}$

$(\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 $\phi(p^{r})=p^{r-1}(p-1)$ and $\phi(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\geq 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>0$ a positive integer. Then $1+p$ has exact order $p^{k-1}$ in the multiplicative group $(\mathbb{Z}/{p^{k}}\mathbb{Z})^{\times}$.

###### Proof.

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

 $(1+p)^{p^{n}}=1+\sum_{i=1}^{p^{n}}\dbinom{p^{n}}{i}p^{i}$

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

 $\operatorname{ord}_{p}\left(\dbinom{p^{n}}{i}p^{i}\right)=n+i-\operatorname{% ord}_{p}(i)$

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

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

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

###### Lemma 4.

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

###### 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}}\dbinom{2^{n}}{i}2^{2i}$

Then

 $\operatorname{ord}_{2}\left(\dbinom{2^{n}}{i}2^{i}\right)=n+2i-\operatorname{% ord}_{2}(i)$

Now, $2i-\operatorname{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}+r2^{n+3},\quad r\in\mathbb{Z}$

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

## References

Title structure of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ as an abelian group StructureOfmathbbZnmathbbZtimesAsAnAbelianGroup 2013-03-22 18:42:40 2013-03-22 18:42:40 rm50 (10146) rm50 (10146) 4 rm50 (10146) Theorem msc 20A05 msc 20E36 msc 20E34