Alternative proofs that the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic

Question

Let $p$ be prime. Every proof of the fact that $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic uses at some point the fact that $x^a = 1 \pmod{p}$ has at most $a$ solutions. Gauss' original two proofs (showing the existence of a primitive root) use this fact and this source actually gives seven proofs, of which only the last one does not use this fact, but that one instead uses heavier machinery with cyclotomic polynomials anyway. It annoys me that this fact is so necessary and I was wondering if there are any proofs without it.

The closest to an alternative proof, that I know of, works when the prime decomposition of $p-1$ contains primes only once, i.e. $p-1 = q_1 q_2\cdots q_n$ for distinct primes $q_i$. Primes below $100$ of this form are $3$, $7$, $11$, $23$, $31$, $43$, $47$, $59$, $67$, $71$, $79$, and $83$.

This alternative proof is due to McKay's proof of Cauchy's Theorem. It suffices to show for each prime $q_i$ that there exists an $a_i$ with order $q_i$, since then the product $a_1 a_2 \cdots a_n$ has order $q_1 q_2 \cdots q_n = p-1$ and so $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic.

So let's fix $q = q_i$ for some $q_i$. Instead of finding an $a \neq 1$ with $a^q \equiv_p 1$, let's solve the simpler problem of finding $(a_1, \ldots ,a_q)$ with $a_1 a_2 \cdots a_q \equiv_p 1$. There are $(p-1)^{q-1}$ such tuples: Fix the first $q-1$ elements and solve for $a_q$. Furthermore, if $(a_1, a_2, \ldots ,a_q)$ is a solution, then the cyclic permutation $(a_q, a_1, \ldots,a_{q-1})$ is one. That means solutions that are permutations of each other come in sets of size $q$, except for the solutions that are their own permutation, i.e. $a_1 = \cdots = a_q$. Let $N$ be the set of such solutions. We have that $|N| = (p-1)^{q-1} - \textit{sets of size }q$. As $p-1$ and $q$ are obviously multiples of $q$, the right side is a multiple of $q$ and therefore $|N|$ is too. But since $N$ contains the solution $(1, \ldots, 1)$, $|N| \geq q$ and therefore there exists a non-trivial solution $(a, \ldots, a)$ with $a^q = 1$. $\tag*{$\Box$}$

I like this alternative proof, because it has a more combinatorial flavour to it and is less algebraic. Again, I'd be thankful for any proof that does not use the fact that $x^a \equiv 1 \pmod p$ has at most $a$ solutions directly. Any deviance from the "standard" would help immensely.

Answer 1

You could prove in general that given a field $F$ and $G$ a finite subgroup of the multiplicative group of $F$ then $G$ is cyclic, and then take $F =\mathbb{F}_{p}^{n}$ and $G = (\mathbb{F}_{p}^{n})^{*}$ looking at $n=1$.

A nice prove of the theorem cited above is given by the structure theorem, and it's the following :

Since $G$ is a finite subgroup of a field we have that $G$ is abelian so

$$G \cong \prod\limits_{i=1}^{k} N_{p_{i}}$$

In other words $G$ is the product of his $p_{i}$-torsion components, which coincide with the $p_{i}$ sylow subgroups. If we prove that for each $i$ $N_{p_{i}}$ is cyclic we've done.

By the structure theorem for finite abelian group we have

$$N_{p_{i}} \cong \mathbb{Z}_{p_{i}^{a_{1}}} \times \cdots \times \mathbb{Z}_{p_{i}^{a_{n}}}$$

With $0 < a_{1} \leq \cdots \leq a_{n}$, and we afirm that exists only one component, let's say $\mathbb{Z}_{p_{i}^{a_{1}}}$.

If by some chance there was even $ \mathbb{Z}_{p_{i}^{a_{2}}}$ we would find in $G$ a subgroup isomorphic to $ \mathbb{Z}_{p_{i}} \times \mathbb{Z}_{p_{i}}$, so we would have at least $p_{i}^{2}$ roots of the polynomial $x^{p_{i}}-1$, which contradicts the fact that a polynomial of degree $n$ with coefficients in a field has at most $n$ roots in the field.

Answer 2

The proof (of a specific case) you give however doesn't have much to do with $(\mathbb Z/p \mathbb Z)^*$ - it proves that any abelian group of squarefree order is cyclic, and ofcourse there is much more to say about $(\mathbb Z/p \mathbb Z)^*$ than that it's abelian. For example, it's a finite subgroup of the multiplicative group of a field, and a more general theorem proves that that means it's cyclic (as mentioned by jacopoburelli too). In this theorem, it is again a key point that $X^d - 1$ has at most $d$ roots.

To show you in another sense that this is pretty essential, I would like to show you the following characterization of finite cyclic groups - which by the way also immediately proves $(\mathbb Z/p\mathbb Z)^*$ is cyclic by using that $X^d - 1$ has at most $d$ roots.

Theorem. A finite group $G$ is cyclic if and only if for every divisor $d \mid \# G$, there exists at most one subgroup of $G$ of order $d$.

This means that for every divisor $d$ of the order of the cyclic group, there can be at most $d$ solutions to $x^d = 1$, since these solutions form a subgroup of order $d$. The ''$\impliedby$'' part of the proof is also essentially the same as one of the proofs from the Keith Conrad paper you linked.

Proof: Note that a cyclic group $G = \langle x \rangle$ has a subgroup of order $d$ for every divisor, since if $\# G = kd$, then $x^k$ has order $d$. Furthermore, a subgroup $H \subseteq G$ of order $d$ has index $k$, so $x^kH = (xH)^k = H$, so $x^k \in H$, so $H = \langle x^k \rangle$.

This proves one direction. For the other direction, write $D$ for the set of orders of elements of $G$. If $g \in G$ has order $d$, then $\langle g \rangle$ is the unique subgroup of order $d$. Thus, $\langle g \rangle$ contains all elements of order $d$. This group has $\varphi(d)$ generators, thus $G$ has $\varphi(d)$ elements of order $d$. So then $$ \# G = \sum_{d \in D} \varphi(d) \leq \sum_{d \mid \# G} \varphi(d) = \# G. $$ Thus $D$ must contain all divisors of $\# G$, so in particular $\# G$ itself. $\tag*{$\Box$}$