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

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.