# Lucas' primality test == finding a primitive root?

I'm looking at some definitions of Lucas' primality test and as far as I can see the algorithm for the examples shown on most sites seem to just be "For some number $n$ if $n$ has a primitive root then $n$ is prime"

Is this a true statement? Conversely, can non-primes also have primitive roots?

-

There is a primitive root modulo $m$ iff $m$ is $2$, $4$, $p^k$, or $2 p^k$, where $p$ is an odd prime.
If $a$ also survives the second step, then the order of $a$ in the group $(Z/nZ)^*$ is equal to $n−1$, which means that the order of that group is $n−1$ (because the order of every element of a group divides the order of the group), implying that $n$ is prime.
@Arvin: The only hard step. An odd number with a primitive root is a prime power, so all you have to do is check if it's a square, a cube, a fifth power, ... up to $\log_2 n$. –  Charles Apr 19 '13 at 2:57