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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I see, so finding a primitive root is only one step of the test. Thanks $\endgroup$
    – Arvin
    Nov 3, 2012 at 15:16
  • $\begingroup$ @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$. $\endgroup$
    – Charles
    Apr 19, 2013 at 2:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .