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?