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

## Referències

* ↑ Crandall & Pomerance (2001), p. 132, Teorema 3.4.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.
* ↑ Baillie, R. and Wagstaff, S. S. Jr. "Lucas Pseudoprimes." Math. Comput. 35, 1391-1417, 1980.
* ↑ Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio «On the generalized Fibonacci pseudoprimes». Fibonacci Quarterly, 28, 1990, pàg. 347–354.
* ↑ Weisstein, Eric W., «Pell Number» a MathWorld (en anglès).

## 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)