Primitive roots for a number

Question

I want to show if a number a is a primitive root$\pmod{n}$
Is there a way to show this without raising a to all the powers between 1 and n-1?

Answer 1

You need not test all powers from $1\dots n-1:\;$ A number $a$ with $\gcd(a,n)=1\;$ is a primitive root $\bmod n\,$ iff
$$a^{\varphi(n)/q} \not \equiv 1 \pmod n$$ for every prime divisor $q$ of $\varphi(n),\,$ where $\varphi(n)$ is Euler's totient function.