Proving a number has no primitive roots

Question

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

Answer 1

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.

Answer 2

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.