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(\mathrm{mod}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\le a\le p-2$ perquè cada nombre senar $p$ satisfà $a^{p-1}\equiv 1(\mathrm{mod}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\ge 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\text{(mod 13)}$

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

$2^{2046}\equiv 1\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(\mathrm{mod}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(\mathrm{mod}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\ne 0$, es definex la seqüència de Lucas

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

per $k\ge 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(\frac{D}{n}\right).$

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

$U_{\delta (n)}\equiv 0(\mathrm{mod}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

• Plantilla:Ref-llibre
• Plantilla:Ref-llibre

Enllaços externs

• Taula dels nombres pseudoprimers de Fermat menors de 5000 Plantilla:De