How do you prove an arbitrary number $n$ has no primitive roots without finding all numbers less than $n$ which are also coprime to $n$ and exhausting that none of the order of these numbers modulo $n$ are equal to $\phi(n)$?


There is a known result about this. It's not especially easy to prove.

Theorem. An integer $n\ge2$ has a primitive root if and only if it is one of the following: $2$, $4$, $p^\alpha$, $2p^\alpha$, where $p$ is prime, $p\ne2$, and $\alpha\ge1$.

So for example $47$ has primitive roots, $48$ doesn't, $49$ does, $50$ does, $51$ doesn't.

  • $\begingroup$ Do you think you can provide a proof of this theorem? I understand that if a number is not of this form that it does not have a primitive root, but I do not understand why that is so. $\endgroup$ – ddresner8 Nov 20 '14 at 5:10
  • $\begingroup$ If you Google "primitive roots theorem" you will find a proof. The first one I looked at was nine pages long, so it's a bit lengthy to give here. $\endgroup$ – David Nov 20 '14 at 5:13
  • $\begingroup$ Pretty much any intro number theory textbook should have a proof, as well. $\endgroup$ – Gerry Myerson Nov 20 '14 at 6:25
  • $\begingroup$ @ddresner8 This article by Amin Witno was my first encounter with a proof of the entire theorem, I can recommend it: philadelphia.edu.jo/math/witno/notes/won5.pdf $\endgroup$ – punctured dusk Nov 20 '14 at 19:41

The key observation, which leads to half of the main theorem, is that

If $n=ab$, where $a,b >1$ are odd and coprime, then $n$ does not have a primitive root because for $m=lcm(\phi(a),\phi(b))$ we have $x^m \equiv 1 \bmod n$ for all $x$ coprime with $n$. Note that $m < \phi(n)$ because $\phi(a)$ and $\phi(b)$ are both even.

The harder part of the main theorem is the existence of primitive roots for primes and powers of primes.


Your Answer

