Pseudoprimo di Fibonacci

In teoria dei numeri, uno pseudoprimo è un numero che passa alcuni test di primalità che passano anche tutti i numeri primi, ma che è composto. Uno pseudoprimo di Fibonacci è un intero composto n che soddisfa le seguenti condizioni:

1. P > 0 e Q = +1 o −1
2. V_n è congruente con P mod n.

In questo caso la notazione usata si riferisce alla sequenza di Lucas con parametri P, Q che produce una sequenza di numeri U_n, V_n.

Uno pseudoprimo di Fibonacci forte può essere definito come segue:

1. Un intero dispari composto n è anche un numero di Carmichael
2. 2(p_i + 1) | (n − 1) o 2(p_i + 1) | (n − p_i) per ogni primo p_i che divide n.

Il più piccolo esempio conosciuto di uno pseudoprimo di Fibonacci forte è 443.372.888.629.441, che ha come fattori 17, 31, 41, 43, 89, 97, 167 e 331.

Bibliografia

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

Collegamenti esterni

• (EN) Anderson, Peter G. Fibonacci Pseudoprimes, their factors, and their entry points.
• (EN) Anderson, Peter G. Fibonacci Pseudoprimes under 2,217,967,487 and their factors.
• (EN) MathWorld: Fibonacci Pseudoprime, su mathworld.wolfram.com.