If

n > 1 is an integer and for each prime factor q of n-1 there is an an integer a such that and a^(n-1)=1 (mod n),

but a^((n-1)/q) != 1 (mod n), then n is prime.

Printable View

- October 8th 2009, 06:12 PMkobulingamTough prime testing question
If

n > 1 is an integer and for each prime factor q of n-1 there is an an integer a such that and a^(n-1)=1 (mod n),

but a^((n-1)/q) != 1 (mod n), then n is prime.

- October 9th 2009, 03:41 AMaidan
I don't see a question.

That is a statement of the Lucas primality test.

An explanation for the correctness of that is here: Lucas primality test - Wikipedia, the free encyclopedia