1
$\begingroup$

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?

1 Answers 1

2

There is a primitive root modulo $m$ iff $m$ is $2$, $4$, $p^k$, or $2 p^k$, where $p$ is an odd prime.

I don't know what sources you mean, so I'm guessing here, but in Wikipedia it says:

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.

This is not quite the same as having a primitive root: it's stronger.

  • 0
    @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$. – 2013-04-19