Lucas pseudoprime

In number theory, the classes of Lucas pseudoprime and Fibonacci pseudoprime comprise sequences of composite integers that passes certain tests that all primes pass: in this case, criteria relative to some Lucas sequence.

Definition

Given two integer parameters P and Q which satisfy

$D = P^2 - 4Q \neq 0 ,$

the Lucas sequences of the first and second kind, U_n(P,Q) and V_n(P,Q) respectively, are defined by the recurrence relations

$U_0(P,Q)=0 \,$

$U_1(P,Q)=1 \,$

$U_n(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q) \mbox{ for }n>1 \,$

and

$V_0(P,Q)=2 \,$

$V_1(P,Q)=P \,$

$V_n(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q) \mbox{ for }n>1 \,$

We can write

$U_n(P,Q) = \frac{a^n-b^n}{a-b} \,$

$V_n(P,Q) = a^n + b^n \,$

where a and b are roots of the auxiliary polynomial X² - P X + Q, of discriminant D.

If p is an odd prime number then

V_p is congruent to P modulo p.

and if the Jacobi symbol

$\left(\frac{D}{p}\right) = \varepsilon \ne 0$,

then p is a factor of U_p-ε.

Lucas pseudoprimes

A Lucas pseudoprime is a composite number n for which n is a factor of U_n-ε. (Riesel adds the condition that the Jacobi symbol $\left(\frac{D}{n}\right)$ should be −1.)

In the specific case of the Fibonacci sequence, where P = 1, Q = -1 and D = 5, the first Lucas pseudoprimes are 323 and 377; $\left(\frac{5}{323}\right)$ and $\left(\frac{5}{377}\right)$ are both −1, the 324th Fibonacci number is a multiple of 323, and the 378th is a multiple of 377.

A strong Lucas pseudoprime is an odd composite number n with (n,D)=1, and n-ε=2^rs with s odd, satisfying one of the conditions

n divides U_s

n divides V_2^js

for some j < r. A strong Lucas pseudoprime is also a Lucas pseudoprime.

An extra strong Lucas pseudoprime is a strong Lucas pseudoprime for a set of parameters (P,Q) where Q = 1, satisfying one of slightly modified conditions

n divides U_s and V_s is congruent to ±2 modulo n

n divides V_2^js

for some j < r. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime.

By combining a Lucas pseudoprime test with a Fermat primality test, say, to base 2, one can obtain very powerful probabilistic tests for primality. See the paper by Baillie and Wagstaff, and the books by Crandall and Riesel.

Fibonacci pseudoprimes

A Fibonacci pseudoprime is a composite number n for which

V_n is congruent to P modulo n

when Q = ±1.

A strong Fibonacci pseudoprime may be defined as a composite number which is a Fibonacci pseudoprime for all P. It follows (see Müller and Oswald) that in this case:

1. An odd composite integer n is also a Carmichael number
2. 2(p_i + 1) | (n − 1) or 2(p_i + 1) | (n − p_i) for every prime p_i dividing n.

The smallest example of a strong Fibonacci pseudoprime is 443372888629441, which has factors 17, 31, 41, 43, 89, 97, 167 and 331.

It is conjectured that there are no even Fibonacci pseudoprimes (see Somer).

See also

• 64079 (number)

References

• Richard E. Crandall; Carl Pomerance (2001). Prime numbers: A computational approach. Springer-Verlag. pp. 131–132. ISBN 0-387-94777-9. 
• Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 (2nd ed ed.). Birkhäuser. p. 130. ISBN 0-8176-3743-5. 
• Müller, Winfried B. and Alan Oswald. "Generalized Fibonacci Pseudoprimes and Probable Primes." In G.E. Bergum et al., eds. Applications of Fibonacci Numbers. Volume 5. Dordrecht: Kluwer, 1993. 459-464.
• Somer, Lawrence. "On Even Fibonacci Pseudoprimes." In G.E. Bergum et al., eds. Applications of Fibonacci Numbers. Volume 4. Dordrecht: Kluwer, 1991. 277-288.
• Richard K. Guy (2004). Unsolved Problems in Number Theory. Springer-Verlag. p. 45. ISBN 0-387-20860-7. 

External links

• Anderson, Peter G. Fibonacci Pseudoprimes, their factors, and their entry points.
• Anderson, Peter G. Fibonacci Pseudoprimes under 2,217,967,487 and their factors.
• Weisstein, Eric W., "Fibonacci Pseudoprime" from MathWorld.
• Weisstein, Eric W., "Lucas Pseudoprime" from MathWorld.
• Weisstein, Eric W., "Strong Lucas Pseudoprime" from MathWorld.
• Weisstein, Eric W., "Extra Strong Lucas Pseudoprime" from MathWorld.