Lucas Pseudoprime
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].
Baillie, R. and Wagstaff, S. S. Jr. "Lucas Pseudoprimes." Math. Comput. 35, 1391-1417, 1980.
Bruckman, P. S. "Lucas Pseudoprimes are Odd." Fib. Quart. 32, 155-157, 1994.
Ribenboim, P. "Lucas Pseudoprimes (lpsp(
))." §2.X.B
in The
New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, p. 129,
1996.
Sloane, N. J. A. Sequence A005845/M5469 in "The On-Line Encyclopedia of Integer Sequences."
Weisstein, Eric W. "Lucas Pseudoprime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LucasPseudoprime.html
Contact the MathWorld Team
.03571428571428...