Número pseudoprimo

Els pseudoprimos són aquells números que, sense ser primers, verifiquen el test de base b, o lo que és lo mateix:

Sent n pertanyent als número entero, es diu que n és pseudoprimo respecte la base b si és compost i ademés verifica la congruència:

$b^{n-1}\equiv 1(\mathrm{mod}n),$

és dir, n dividix a b^n-1-1.

Esta propietat és un cas particular del Menuda Teorema de Fermat i per tant sempre es verifica per a número primo.

Eixemples

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

Ací es verifica l'equació puix 13 és primer.

$2^{2046}\equiv 1(\mathrm{mod}2047)$

Ací es verifica l'equació per a 2047=23×89. Llavors 2047 és un pseudoprimo en base 2.