Nombre pseudoprimer

Els nombres pseudoprimers són els que no essent primers, verifiquen el test de primalitat de base b:

Siguin un nombre enter i un altre nombre enter no primer. El nombre és pseudoprimer respecte a la base si .

Els nombres pseudoprimers respecte qualsevol base són els nombres de Carmichael.

Pseudoprimers de FermatModifica

El petit teorema de Fermat estableix que si   és primer i   és coprimer amb  , llavors   és divisible per  . Per a un nombre enter  , si un nombre enter compost   divideix  , llavors   s'anomena pseudoprimer de Fermat en base  . D'això es desprèn que si   és un pseudoprimer de Fermat en base  , llavors   és coprimer de  . Algunes fonts utilitzen variacions d'aquesta definició, per exemple per fer que només els nombres imparells puguin ser pseudoprimers.

Quan un enter   és pseudoprimer de Fermat a tots els valors de   que són primers entre si per  , s'anomena nombre de Carmichael.

És suficient que la base   satisfaci   perquè cada nombre senar   satisfà   per  .[1]

Si   és un pseudoprimer de Fermat en base   llavors   també és un pseudoprimer de Fermat en base   per tot enter  .

Un nombre pseudoprimer de Fermat sempre ho és per un nombre parell de bases, atès que cada base té una cobase vàlida tal que  .

La majoria de nombres pseudoprimers, com els pseudoprimers d'Euler, de Fibonacci o de Lucas, també són pseudoprimers de Fermat.

ExemplesModifica

 

En aquest cas es verifica l'equació, ja que 13 és un nombre primer.

 

Aquí es verifica l'equació per 2047 = 23×89. Llavors n es un nombre pseudoprimer en base 2.

Altres definicions de nombres pseudoprimersModifica

Pseudoprimer de CatalanModifica

Un pseudoprimer de Catalan és un nombre compost imparell n que satisfà la congruència

 

on   denota el nombre de Catalan d'índex m.[2]

La seqüència de pseudoprimers de Catalan es pot consultar a l'OEIS A163209

En general, si   és un primer de Wieferich, llavors   és un pseudoprimer de Catalan.

Pseudoprimer d'EulerModifica

Un pseudoprimer d'Euler és un nombre compost imparell n que per una base natural a, satisfà:

 

on m és 1 o bé -1.

Tot pseudoprimer d'Euler és també un pseudoprimer de Fermat. A més, un pseudoprimer d'Euler també s'anomena pseudoprimer d'Euler-Jacobi quan m correspon al símbol de Jacobi  .

Un pseudoprimer absolut d'Euler és aquell que compleix l'equació per a tota base a coprimer de n, i per tant, també és per definició un nombre de Carmichael.

Pseudoprimer de LucasModifica

Quan P i Q són enters tals que  , es definex la seqüència de Lucas

 

per   essent a i b les dues arrels del polinomi  .

Baillie i Wagstaff defineixen un pseudoprimer de Lucas com un nombre compost imparell tal que el símbol de Jacobi   és -1 i  , on   són els nombres de Lucas.[3] Definim:

 

Si n i Q són coprimers, llavors es compleix la següent congruència:

 

En altres paraules, donats uns valors (P, Q), un nombre n compost és un pseudoprimer de Lucas si l'equació anterior es compleix.

Quan P = 1 i Q = -1,   correspon als nombres de Fibonacci, per tant a aquest subgrup de nombres se'ls anomena pseudoprimers de Fibonacci.[4]

De manera similar, per valors P = 2 i Q = −1 s'obtenen els nombres de Pell, i per tant a aquest subgrup se'ls anomena pseudoprimers de Pell.[5]

AltresModifica

Existeixen altres subgrups de pseudoprimers, relacionats amb els ja esmentats:

  • Pseudoprimer el·líptic
  • Pseudoprimer de Frobenius
  • Pseudoprimer de Dickson
  • Pseudoprimer de Perrin
  • Pseudoprimer de Somer–Lucas
  • Pseudoprimer fort i extra-fort

ReferènciesModifica

  1. Crandall & Pomerance (2001), p. 132, Teorema 3.4.2.
  2. Aebi, Christian; Cairns, Grant «Catalan numbers, primes and twin primes». Elemente der Mathematik, 63, 4, 2008, pàg. 153–164. DOI: 10.4171/EM/103.
  3. Baillie, R. and Wagstaff, S. S. Jr. "Lucas Pseudoprimes." Math. Comput. 35, 1391-1417, 1980.
  4. Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio «On the generalized Fibonacci pseudoprimes». Fibonacci Quarterly, 28, 1990, pàg. 347–354.
  5. Weisstein, Eric W., «Pell Number» a MathWorld (en anglès).

BibliografiaModifica

  • Richard E. Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001. ISBN 0-387-25282-7. 
  • Paulo Ribenboim. The New Book of Prime Number Records. Springer-Verlag, 1996. ISBN 0-387-94457-5. 

Enllaços externsModifica