Luke's Pseudo-Simple Number

In number theory, the classes of pseudo-simple Luke numbers and pseudo-simple Fibonacci numbers consist of Luc numbers that have passed some tests, which all primes satisfy.

Content

Base property

Consider the Lucas sequences U _n ( P , Q ) and V _n ( P , Q ), where the integers P and Q satisfy the condition:

D=P^{2}-4Q\neq 0.

{\ displaystyle D = P ^ {2} -4Q \ neq 0.}

Then, if p is a prime greater than 2, then

V_{p}\equiv P{\pmod {p}}

{\ displaystyle V_ {p} \ equiv P {\ pmod {p}}}

and if the Jacobi symbol

\left({\frac {D}{p}}\right)=\varepsilon \neq 0,

{\ displaystyle \ left ({\ frac {D} {p}} \ right) = \ varepsilon \ neq 0,}

then p divides U _p-ε .

Pseudo-Simple Luke

Luke's pseudo-simple ^[1] is a composite number n that divides U _n-ε . (Riesel adds a condition: the Jacobi symbol $\left({\tfrac {D}{n}}\right)=-1$ ${\ displaystyle \ left ({\ tfrac {D} {n}} \ right) = - 1}$ .)

In the particular case of the Fibonacci sequence , when P = 1, Q = −1 and D = 5, the first pseudo-simple Luc numbers are 323 and 377; $\left({\tfrac {5}{323}}\right)$ ${\ displaystyle \ left ({\ tfrac {5} {323}} \ right)}$ and $\left({\tfrac {5}{377}}\right)$ ${\ displaystyle \ left ({\ tfrac {5} {377}} \ right)}$ both are −1, the 324th Fibonacci number is divided by 323, and the 378th is divided by 377.

Luke's strong pseudo-simple 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 . Luke's pseudo-simple is also Luke's pseudo-simple.

Luke's superstrong pseudo-simple is Luke 's strong pseudo-simple for the set of parameters ( P , Q ), where Q = 1, satisfying one of the slightly modified conditions:

n divides U _s and V _s , comparable to ± 2 modulo n

n divides V _{2 ^j s}

for some j < r . Luke's superstrong pseudo-simple is also Luke's strong pseudo-simple.

By combining the Lucas pseudo- simplicity test with Fermat's simplicity test , say, modulo 2, one can obtain very strong probabilistic simplicity tests.

Pseudo Simple Fibonacci

A Fibonacci pseudo-simple is a composite number, n for which

V _n is comparable to P modulo n ,

where Q = ± 1.

A strong pseudo-simple Fibonacci can be defined as a compound number, which is a pseudo-simple Fibonacci number for any P. It follows from the definition (see Müller and Oswald) that:

An odd compound integer n , which is also a Carmichael number
2 ( p _i + 1) | ( n - 1) or 2 ( p _i + 1) | ( n - p _i ) for any prime p _i dividing n .

The smallest strong pseudo-simple Fibonacci number is 443372888629441, which has divisors 17, 31, 41, 43, 89, 97, 167 and 331.

It has been suggested that there are no even pseudo-simple Fibonacci numbers ^[2]

Notes

↑ Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprimes (Eng.) // Mathematics of Computation : journal. - 1980 .-- October ( vol. 35 , no. 152 ). - P. 1391-1417 . - DOI : 10.1090 / S0025-5718-1980-0583518-6 .
↑ Somer, Lawrence. On Even Fibonacci Pseudoprimes // Applications of Fibonacci Numbers / GE Bergum et al .. - Kluwer, 1991. - Vol. 4. - P. 277-288.

Literature

Richard E. Crandall . Prime numbers: A computational approach. - Springer-Verlag , 2001. - P. 131-132. - ISBN 0-387-94777-9 .
Hans Riesel. Prime Numbers and Computer Methods for Factorization. - 2nd ed. - Birkhäuser, 1994. - Vol. 126. - P. 130. - ISBN 0-8176-3743-5 .
Müller, Winfried B. and Alan Oswald. "Generalized Fibonacci Pseudoprimes and Probable Primes." In GE Bergum et al., Eds. Applications of Fibonacci Numbers. Volume 5. Dordrecht: Kluwer, 1993. 459-464.
Richard K. Guy . Unsolved Problems in Number Theory. - Springer-Verlag, 2004. - P. 45. - ISBN 0-387-20860-7 .

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.
Weisstein, Eric W. Fibonacci Pseudoprime on the Wolfram MathWorld website.
Weisstein, Eric W. Lucas Pseudoprime on the Wolfram MathWorld website.
Weisstein, Eric W. Strong Lucas Pseudoprime on the Wolfram MathWorld website.
Weisstein, Eric W. Extra Strong Lucas Pseudoprime on the Wolfram MathWorld website.

[1] Robert Baillie; Samuel S. Wagstaff, Jr. Lucas Pseudoprimes (Eng.) // Mathematics of Computation : journal. - 1980 .-- October ( vol. 35 , no. 152 ). - P. 1391-1417 . - DOI : 10.1090 / S0025-5718-1980-0583518-6 .

[2] Somer, Lawrence. On Even Fibonacci Pseudoprimes // Applications of Fibonacci Numbers / GE Bergum et al .. - Kluwer, 1991. - Vol. 4. - P. 277-288.