Proof of existence of primitive roots

In my book (Elementary Number Theory, Stillwell), exercise 3.9.1 asks to give an alternative proof of the existence of a primitive root for any prime.

Let $p$ be prime, and consider the group $\mathbb{Z}/p\mathbb{Z}$.

Suppose that the non-zero elements $\text{mod}\ p$ have maximum order $n < p - 1$. Show that this implies $x^n \equiv 1 \ (\text{mod}\ p)$ for all the $p - 1$ non-zero values of $x$, $\text{mod}\ p$, contrary to Lagrange's polynomial congruence theorem.

What I've considered so far is that all non-zero elements of the group $\mathbb{Z}/p\mathbb{Z}$ generate subgroups of order $k \leq n < p - 1$, such that $k \mid p - 1$ (by Lagrange's theorem for groups). Showing that $k \mid n$ eludes me however. Any further ideas?

Solution 1:

Let $n$ be the maximum order. To prove that $x^n\equiv 1\pmod{p}$, it is enough to show that the order of $x$ divides $n$.

Let $a$ be an element of maximum order, and suppose that the order $m$ of $x$ does not divide $n$. Then the lcm $\ell$ of $m$ and $n$ is greater than $n$. We show that there is an element of order $\ell$, contradicting the maximality of $n$.

By considering the prime power factorization of $m$ and $n$, we can find $m'$, $n'$ such that $m'$ divides $m$, and $n'$ divides $n$, and $\gcd(m',n')=1$, and $m'n'=\ell$.

Using $x$, we can construct an element of order $m'$, and using $a$ we can construct an element of order $n'$. But since $\gcd(m',n')=1$, we can construct an element of order $m'n'$, and we are finished.

Added: The following standard result was used in the construction:

Lemma: If $a$ has order $h$ modulo $p$, and $b$ has order $k$, where $\gcd(h,k)=1$, then $ab$ has order $hk$.

Proof: Let $r$ be the order of $ab$. Since $(ab)^{hk}\equiv 1\pmod{p}$, it follows that $r$ divides $hk$. We will show that $hk$ divides $r$.

Note that since $b^k\equiv 1$, we have $$a^{rk}\equiv a^{rk}b^{rk}\equiv 1\pmod{p}.$$ It follows that $h$ divides $rk$. Since $\gcd(h,k)=1$, it follows that $h$ divides $r$. Similarly, $k$ divides $r$. But since $\gcd(h,k)=1$, it follows that $hk$ divides $r$. This completes the proof.