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.

  • 2
    $\begingroup$ The proof is not just a paragraph long. Fortunately, the full proof will be in many textbooks on elementary number theory (for example, the book of Niven/Zuckerman/Montgomery, Section 2.8). It's probably better to seek out that proof than to ask someone to copy pages of math down. $\endgroup$ – Greg Martin Oct 4 '16 at 4:04
  • $\begingroup$ Unfortunately I don't own the textbook, but a qualitative/intuitive proof would be okay with me. $\endgroup$ – PiccolMan Oct 4 '16 at 15:04

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.