Nombre pseudoprimer

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

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

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

Pseudoprimers de Fermat

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

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

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

Si $p$ és un pseudoprimer de Fermat en base $a$ llavors $p$ també és un pseudoprimer de Fermat en base $b\cdot p+a$ per tot enter $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 $a^{*}=p-a$.

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

Exemples

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

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

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

Altres definicions de nombres pseudoprimers

Pseudoprimer de Catalan

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

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

on $C_{m}$ denota el nombre de Catalan d'índex m.

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

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

Pseudoprimer d'Euler

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

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

Pseudoprimer de Lucas

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

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

per $k\geq 0$ essent a i b les dues arrels del polinomi $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 $D/n$ és -1 i $n|(L_{n}-1)$, on $L_{n}$ són els nombres de Lucas. Definim:

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

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

$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, $U_{n}(P,Q)$ correspon als nombres de Fibonacci, per tant a aquest subgrup de nombres se'ls anomena pseudoprimers de Fibonacci.

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.

Altres

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

Bibliografia

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

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