Ricordiamo che due interi a, b, si dicono coprimi se non hanno fattori in comune diversi da 1. Se p è primo, asserire che a è coprimo con p equivale a dire che p non divide a.
Il PTF (Piccolo Teorema di Fermat) afferma che:
se p è un numero primo ed a è un intero coprimo con p,
allora p divide ap-1 - 1
Per esempio 17 divide 65535 = 216 - 1.
Un numero n che divide an-1 - 1, si dice probabilmente primo sulla base a.
Per il PTF ogni primo p è probabilmente primo su qualsiasi base a coprima con p.
Diciamo pseudoprimo sulla base a un numero composto probabilmente primo su a. Facendo un po' di conti, il più piccolo pseudoprimo sulla base 2 che incontriamo è 341, infatti:
341 = 11 31 e 341 divide 2340 - 1.
Si noti che 341 non risulta probabilmente primo sulla base 3.
David Carmichael (1879 - 1967) fu un matematico assai versatile, scrisse molti libri importanti su argomenti che vanno dalla relatività, ai gruppi finiti, alla teoria dei numeri.
I numeri di Carmichael sono interi positivi n che soddisfano alla seguente condizione:
se a è un intero coprimo con n allora n divide an-1 - 1
Dunque i numeri di Carmichael sono, proprio come i numeri primi, probabilmente primi su ogni possibile base.
Il più piccolo di questi numeri è 561 = 3 11 17.
Si dimostra (Korselt 1899) che:
un intero n è un numero di Carmichael
se e solo se valgono la (1) e la (2):
(1) n = p1 p2...pk, dove i pi sono primi distinti
(2) per ogni i, pi - 1 divide n - 1
Per esempio 561 è di Carmichael perché è il prodotto dei tre primi distinti 3, 11, 17 ed inoltre 2, 10, 16 dividono 560.
I numeri di Carmichael sono molto rari, sotto 100000 sono:
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341,
41041, 46657, 52633, 62745, 63973, e 75361.
Ce ne sono 2163 minori di 25 miliardi, e appena 246683 minori di 1016.
Nel 1910 Carmichael calcolò i primi 15, e congetturò che fossero infiniti.
Nel 1956 Erdös ideò una tecnica per fabbricare numeri di Carmichael grandi.
Nel 1994 si provò che sono infiniti:
W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers," Ann. of Math. (2), 139 (1994) 703--722