Tough prime testing question

kobulingam · #1 $Old$ October 8th, 2009, 06:12 PM

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.

aidan · #2 $Old$ October 9th, 2009, 03:41 AM

Quote:

Originally Posted by kobulingam $View Post$

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.

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