Primitive Root Theorem Proof

The primitive root theorem states that $U(n)$ is a cyclic group if and only if $n$ is $1, 2, 4, p^{k}, 2p^{k}$ where $p$ is an odd prime and $k$ is an integer greater than or equal to 1. Can someone please prove this for me? I was trying to prove this using the definition of group order, but that did not work.

Solution 1:

Note that the relevant number theory term is "primitive root", which is a generator of the cyclic group $U(n)$ when that group is indeed cyclic. The general outline of establishing which moduli have primitive roots goes like this.

• $1,2,4$ have primitive roots: do by hand.
• Odd primes $p$ have primitive roots: follows from unique factorization of polynomials over $\Bbb F_p$ (shows that low orders of elements can't be too prevalent).
• Powers of odd primes $p$: follows from "lifting" polynomial solutions (Hensel's lemma)
• Twice a power of an odd prime: easy to show that $U(2p^k)$ is naturally isomorphic to $U(p^k)$ when $p$ is odd
• $2^k$ with $k\ge3$: show that $\{\pm5^1,\pm5^2,\dots,\pm5^{2^{k-2}}\}$ form a reduced residue system, and in particular that every element has order at most $2^{k-2}$.
• All other numbers can be factored as $jk$ where $(j,k)=1$ and $j,k>2$; in this case, all elements have order at most $\frac12\phi(jk) = \phi(j)\frac{\phi(k)}2 = \frac{\phi(j)}2\phi(k)$.