Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
I see, so finding a primitive root is only one step of the test. Thanks – Arvin Nov 3 '12 at 15:16
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.