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 D 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.

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).

References

• 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.

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.

fr:Nombre pseudopremier de Fibonacci it:Pseudoprimo di Fibonacci