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 eq 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} ight) = varepsilon e 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} ight) and $$left(frac{5}{377} ight) 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^"r""s" with "s" odd, satisfying one of the conditions

: "n" divides "U"_"s": "n" divides "V"_2^"j""s"

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:

#An odd composite integer "n" is also a Carmichael number
#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. [http://www.cs.rit.edu/usr/local/pub/pga/fpp_and_entry_pts Fibonacci Pseudoprimes, their factors, and their entry points.]
* Anderson, Peter G. [http://www.cs.rit.edu/usr/local/pub/pga/fibonacci_pp Fibonacci Pseudoprimes under 2,217,967,487 and their factors.]
*
*
*
*