Jump to content

Fibonacci pseudoprime

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Just Another Dan (talk | contribs) at 10:21, 29 June 2004 (style, tidy MathWorld link). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In number theory, a pseudoprime is a number that passes some test that all primes pass, but is actually composite. A Fibonacci pseudoprime is a composite integer n that satisfies the following conditions:

  1. P > 0 and Q = +1 or −1
  2. Vn is congruent to P mod n.

Here the notation refers to the Lucas sequence with parameters P, Q producing a series of numbers Un, Vn.

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

A strong Fibonacci pseudoprime may defined as follows (see Müller and Oswald):

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

References

  • Müller, Winfired 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, Larence. "On Even Fibonacci Pseudoprimes." In G.E. Bergum et al, eds. Applications of Fibonacci Numbers. Volume 4. Dordrecht: Kluwer, 1991. 277-288.