Il piccolo Teorema di Fermat afferma che, se P è un numero primo, allora:
A(P-1) ≡ 1 (mod. P)
Per ogni A minore di P ed, in generale, per ogni A coprimo con P.
Cioè, se P è un numero primo, allora A(P-1) – 1 è divisibile per P per ogni A coprimo con P.
Ma non è affatto vero il contrario, cioè se la congruenza è verificata per ogni A inferiore ad un numero N, coprimo con N, non è detto che N sia un numero primo.
Cioè, se A(N-1) – 1 è divisibile per N per ogni A coprimo con N, non è una prova che N sia primo.
Ricordiamo che A si definisce coprimo con N se non ha fattori primi in comune con N, eccetto 1.
I numeri N non primi che soddisfano questa congruenza per ogni A coprimo con N, sono detti “Numeri di Carmichael”. Essi sono piuttosto rari, ma infiniti: tra 1 e 1018 ce ne sono, in media, uno ogni 700 miliardi di numeri.
I numeri di Carmichael sono:
561 1105 1729 2465 2821 6601 8911 10585 15841 29341 41041 46657 52633 62745 63973 75361 ……
Nel 1899 il matematico Korselt scoprì che un numero intero N è un numero di Carmichael se non è divisibile per quadrati esatti e se, per ogni suo fattore primo P, (N-1) è divisibile per (P-1).
Per esempio, il numero di Carmichael 561 ( = 3x11x17) non è divisibile per nessun quadrato esatto ed inoltre 560 è divisibile per 2, 10 e 16.
Nel 1939 il matematico Chernick dimostrò che, se 6K+1, 12K+1 e 18K+1 sono numeri primi, allora il loro prodotto è un numero di Charmichael, ma non tutti i numeri di Chermichael sono di questa forma. Il primo è:
1729 = 7x13x19
Con 7 = 6×1+1 13 = 12×1+1 e 19 = 18×1+1
Un numero non primo che soddisfa la congruenza
A(N-1) ≡ 1 (mod. N)
Per un certo A, viene detto “Numero Pseudoprimo in base A”. I numeri di Carmichel sono dunque pseudoprimi “forti”, cioè pseudoprimi in tutte le basi.
Il più piccolo pseudoprimo in base 2 è 341 che è pseudoprimo in 120 basi su 340.
Il più piccolo pseudoprimo in base 3 è 91 che è pseudoprimo in 48 basi su 90.
Giuseppemerlino's Blog 