Nombre pseudoprimer

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

Siguin ${\displaystyle a}$ un nombre enter i ${\displaystyle p}$ un altre nombre enter no primer. El nombre ${\displaystyle p}$ és pseudoprimer respecte a la base ${\displaystyle a}$ si ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.

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

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

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

És suficient que la base ${\displaystyle a}$ satisfaci ${\displaystyle 2\leq a\leq p-2}$ perquè cada nombre senar ${\displaystyle p}$ satisfà ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ per ${\displaystyle a=p-1}$.^[1]

Si ${\displaystyle p}$ és un pseudoprimer de Fermat en base ${\displaystyle a}$ llavors ${\displaystyle p}$ també és un pseudoprimer de Fermat en base ${\displaystyle b\cdot p+a}$ per tot enter ${\displaystyle b\geq 0}$.

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 ${\displaystyle a^{*}=p-a}$.

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

${\displaystyle 2^{12}\equiv 1\quad {\text{(mod 13)}}}$

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

${\displaystyle 2^{2046}\equiv 1\quad {\text{(mod 2047)}}}$

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

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

${\displaystyle (-1)^{\frac {n-1}{2}}\cdot C_{\frac {n-1}{2}}\equiv 2{\pmod {n}},}$

on ${\displaystyle C_{m}}$ denota el nombre de Catalan d'índex m.^[2]

En general, si ${\displaystyle p}$ és un primer de Wieferich, llavors ${\displaystyle p^{2}}$ és un pseudoprimer de Catalan.

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

${\displaystyle a^{\frac {n-1}{2}}\equiv m{\pmod {n}},}$

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 ${\displaystyle a/n}$.

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.

Quan P i Q són enters tals que ${\displaystyle D=P^{2}-4Q\neq 0}$, es definex la seqüència de Lucas

${\displaystyle U_{k}={\frac {a^{k}-b^{k}}{a-b}}}$

per ${\displaystyle k\geq 0}$ essent a i b les dues arrels del polinomi ${\displaystyle x^{2}-Px+Q=0}$.

Baillie i Wagstaff defineixen un pseudoprimer de Lucas com un nombre compost imparell tal que el símbol de Jacobi ${\displaystyle D/n}$ és -1 i ${\displaystyle n|(L_{n}-1)}$, on ${\displaystyle L_{n}}$ són els nombres de Lucas.^[3] Definim:

${\displaystyle \delta (n)=n-\left({\tfrac {D}{n}}\right).}$

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

${\displaystyle U_{\delta (n)}\equiv 0{\pmod {n}}.}$

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, ${\displaystyle U_{n}(P,Q)}$ 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]

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

• 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. 

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