Vés al contingut

Nombre pseudoprimer

De la Viquipèdia, l'enciclopèdia lliure

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 Fermat

[modifica]

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.

Exemples

[modifica]

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 pseudoprimers

[modifica]

Pseudoprimer de Catalan

[modifica]

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'Euler

[modifica]

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 Lucas

[modifica]

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]

Altres

[modifica]

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ències

[modifica]
  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).

Bibliografia

[modifica]

Enllaços externs

[modifica]
  • Taula dels nombres pseudoprimers de Fermat menors de 5000 (alemany)