Information as of 2020-04-07: Inserting more history entries for Riesel primes k<300

# Lucas primality test

The Lucas primality test invented in 1891 by Édouard Lucas, determines whether a number N is prime or not, using the complete factorization of N-1.

If, for some integer b, the quantity bN-1 is congruent to 1 modulo N, and if b(N-1)/q is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime.

### Example

Prove that N = 811 is prime knowing that N-1 = 2 × 34 × 5

$3^{810/2}\,= \,3^{405}\,\equiv \, 810\,\pmod{811}$
$3^{810/3}\,= \,3^{270}\,\equiv \, 680\,\pmod{811}$
$3^{810/5}\,= \,3^{162}\,\equiv \, 212\,\pmod{811}$
$3^{810}\,\equiv \, 1\,\pmod{811}$
$7^{810/2}\,= \,7^{405}\,\equiv \, 1\,\pmod{811}$