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.]
*
*
*
*