Cosa sono e esempio di Numeri pseudoprimi e numeri di Carmichael
I numeri di Carmichael
Esistono numeri composti come:
561 (il prodotto di 3, 11 e 17)
1729 (il prodotto di 7, 13 e 19)
che, pur rispettando il Piccolo Teorema di Fermat, si comportano come se fossero numeri primi ma non lo sono. Tali numeri sono detti numeri di Carmichael.
Infatti tali numeri composti, relativamente al piccolo teorema di Fermat, si comportano come se fossero primi, ma la condizione espressa dal teorema non vale per tutti i valori di b appartenenti all’intervallo [1,p-1].
Esempio numeri di Carmichael
Consideriamo il numero composto 341 (il prodotto di 11 e 31), è infatti:
1341(mod 341)=1
2341(mod 341)=2
3341(mod 341)=168
4341(mod 341)=4
5341(mod 341)=335
6341(mod 341)=336
7341(mod 341)=51
8341(mod 341)=8
9341(mod 341)=262
…………………….
Effettuando i calcoli per tutte le basi b (da 1 a 340), diremo che 341 è uno pseudoprimo solo rispetto a 120 basi su 340.
Esempio 2 numeri di Carmichael
Il numero composto 91 (il prodotto di 7 e 13), è uno pseudoprimo rispetto a 48 basi su 90.
Il numero composto 15 (il prodotto di 3 e 5), è uno pseudoprimo rispetto a 8 basi su 14.
OSSERVAZIONE
Fortunatamente, nei confronti dei numeri primi, i numeri di Carmichael, numeri pseudoprimi per ogni base, sono molto rari. Non è così, invece, per i numeri pseudoprimi per alcune basi (come i numeri di cui sopra: 341, 91 e 15).