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?
Best Answer
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.