When 
and 
are integers such that 
, define the Lucas
sequence 
by
 |
for 
,
with 
and 
the two roots of 
. Then define a Lucas pseudoprime as an odd composite number 
such that 
, the Jacobi symbol 
, and 
.
The congruence 
holds for every prime number 
, where 
is a Lucas number. However,
some composites also satisfy this congruence. The Lucas pseudoprimes corresponding
to the special case of the Lucas numbers 
are those composite numbers 
such that 
. The first few of these are 705, 2465, 2737, 3745,
4181, 5777, 6721, ... (OEIS A005845).
The Wolfram Language implements the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test in the function PrimeQ[n].
))." §2.X.B in