Group of units modulo prime is cyclic

Statement

Let $p$ be a prime number, then the group of units $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ is a cyclic group of order $p-1$ .

Denote $\varphi$ as the Euler totient function.

It is a standard number theory result that $n=\sum _{d\mid n}\varphi (d)$ , so $p-1=\sum _{d\mid (p-1)}\varphi (d)$ .

We know that if $a\in (\mathbb {Z} /p\mathbb {Z} )^{\times }$ that the order of $a$ divides $p-1$ by Lagrange's theorem.

Let $n_{d}$ be the number of elements of order $d$ in $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ of order $d$ , then $\sum _{d\mid (p-1)}n_{d}=p-1.$

What we want to show is that $n_{p-1}>0$ (so there is an element of order $p-1$ .

Suppose instead $n_{p-1}=0$ . Then $\sum _{d\mid (p-1)}n_{d}=p-1=\sum _{d\mid (p-1)}\varphi (d).$

We know $\varphi (p-1)>0$ . If $n_{p-1}=0$ then we must have $n_{d}>\varphi (d)$ for some $d\mid (p-1)$ .

Let $a\in (\mathbb {Z} /p\mathbb {Z} )^{\times }$ be some element of order $d$ .

Consider the cyclic subgroup $\langle a\rangle$ that it generates. It is cyclic of order $d$ so it has $\varphi (d)$ elements of order $d$ .

We know $n_{d}>\varphi (d)$ so there must exist another element $a'$ of order $d$ not contained in this subgroup.

But this is a contradiction because $\{1,a,\dots ,a^{d-1},a'\}$ are $d+1$ distinct solutions to $X^{d}-1=0$ in $\mathbb {Z} /p\mathbb {Z}$ .

But a result from number theory, (also called Lagrange's theorem but unrelated to the Lagrange's theorem of group theory), says otherwise.

Thus, the group is cyclic.

Group of units modulo prime power is cyclic states that $(\mathbb {Z} /p^{k}\mathbb {Z} )^{\times }$ is cyclic for $p$ prime, $k\in \mathbb {Z}$ . This is the case $k=1$ .