Nombre pseudo-premier de Fibonacci

En théorie des nombres, un nombre pseudo-premier est un nombre qui partage une propriété commune à tous les nombres premiers sans être lui-même premier.

Il existe plusieurs définitions, non équivalentes, de nombre pseudo-premier de Fibonacci. L'une d'elles[1] est[2] :

Un nombre pseudo-premier de Fibonacci est un nombre composé impair n tel que

L n ≡ 1   mod   n , {\displaystyle L_{n}\equiv 1\ {\bmod {\ }}n,}

où L n {\displaystyle L_{n}} est le nombre de Lucas d'ordre n.

Il est conjecturé que la condition d'imparité est redondante[3].

Les premières valeurs en sont 705, 2465, 2737, 3745, 4181, 5777, 6721 : elles forment la suite A005845 de l'OEIS dont les termes y sont dénommés "nombres pseudo-premiers de Bruckman-Lucas".

Un nombre pseudo-premier de Fibonacci fort est un nombre composé impair n tel que[2]

∀ P ∈ Z V n ( P , − 1 ) ≡ P   mod   n {\displaystyle \forall P\in \mathbb {Z} \quad V_{n}(P,-1)\equiv P\ {\bmod {\ }}n}

où V ( P , Q ) {\displaystyle V(P,Q)} est la suite de Lucas de paramètres P et Q. Ce sont des pseudo-premiers de Fibonacci car V n ( 1 , − 1 ) = L n {\displaystyle V_{n}(1,-1)=L_{n}} .

Une condition équivalente est [2]:

  1. n est un nombre de Carmichael ;
  2. pour tout facteur premier p de n, 2(p + 1) divise n – 1 ou n – p.

Le plus petit exemple de pseudo-premier de Fibonacci fort est 443372888629441 = 17·31·41·43·89·97·167·331 ; voir la suite A299799 de l'OEIS.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fibonacci pseudoprime » (voir la liste des auteurs)

, fusionné depuis dans « Lucas pseudoprime (en) ».

  1. ↑ Une définition différente est celle commune à
    • (en) David Bressoud et Stan Wagon, A Course in Computational Number Theory, Key College Publishing in cooperation with Springer, , 367 p. (ISBN 978-1-930190-10-8), p. 264,
    • (en) Richard Crandall et Carl Pomerance, Prime Numbers : A Computational Perspective, Springer Science+Business Media, , 2e éd. (lire en ligne), p. 142 et
    • (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer-Verlag, , 541 p. (ISBN 978-0-387-94457-9), p. 127.
    Une autre encore est donnée dans (en) Eric W. Weisstein, « Fibonacci Pseudoprime », sur MathWorld.
  2. ↑ a b et c (en) Winfried B. Müller et 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 DOI 10.1007/978-94-011-2058-6_45.
  3. ↑ (en) Lawrence Somer, « On Even Fibonacci Pseudoprimes. » In G.E. Bergum et al, eds. Applications of Fibonacci Numbers. Volume 4. Dordrecht: Kluwer, 1991. 277-288 DOI 10.1007/978-94-011-3586-3_31.

Liens externes

  • (en) Peter G. Anderson, Fibonacci Pseudoprimes, their factors, and their entry points
  • (en) Peter G. Anderson, Fibonacci Pseudoprimes under 2,217,967,487 and their factors
  • icône décorative Arithmétique et théorie des nombres