Is there a group theoretic proof that $(\mathbf Z/(p))^\times$ is cyclic?

Question

Theorem: The group $(\mathbf Z/(p))^\times$ is cyclic for any prime $p$.

---

Most proofs make use of the fact that for $r\geq 1$, there are at most $r$ solutions to the equation $x^r=1$ in $\mathbf Z/(p)$, a result which doesn't seem — understandably — to have any group theoretic proofs.

K. Conrad gives seven different proofs — and hints at some others — in his paper here. The first six make use of the previously mentioned fact, while the seventh proof makes extensive use of cyclotomic polynomials and is thus still not group-theoretic.

I was also able to find a linear algebra based proof in the second chapter of Teoría Elemental de Grupos by Emilio Bujalance García, but still, no group theoretic proof to be found.

Answer 1

The fact in the OP ($x^r\equiv 1\pmod p$ has at most $r$ solutions) shows immediately that $({\bf Z}/(p))^\times$ can't have any subgroup isomorphic to $C_q\times C_q$, for any prime $q$ dividing $p-1$ (as otherwise $x^q\equiv 1\pmod p$ would have at least $q^2$ solutions). By the structure theorem for finite abelian groups, $({\bf Z}/(p))^\times$ is cyclic. Another way to show that there cannot be a subgroup isomorphic to $C_q\times C_q$ is recalling that $({\bf Z}/(p))^\times\cong\operatorname{Aut}({\bf Z}/(p))$ acts regularly (by automorphisms) on the set of generators of ${\bf Z}/(p)$. But again this uses the fact the OP would like to avoid. So, take this answer as a long comment, actually.