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.
 A: 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)$.

