Numeri di Carmichael

Un numero di Carmichael è un numero intero positivo \( n \) composto (cioé non primo) che si comporta come un numero primo nel test di Fermat con ogni intero \( 1<a<n \) coprimo con \( n \) ovvero tale che \( MCD(a, n) = 1 \)).

In altre parole, un numero di Carmichael soddisfa la stessa proprietà del piccolo teorema di Fermat che caratterizza i numeri primi, ma senza essere primo.

\[ a^{n-1} \equiv 1 \pmod{n}\]

Questo vuole dire che \( n \) è pseudoprimo con tutti i numeri \( a \) relativamente primi tra 1 e \( n \)

Quindi, è un falso positivo nel test di primalità di Fermat. Sembra un numero primo... ma non lo è.

Nota. I numeri di Carmichael sono infiniti. Il numero più piccolo è il \( 561 \), seguito da \( 1105 \), \( 1729 \), \( 2465 \), \( 2821 \), ecc.

Un esempio pratico

Un esempio classico del numero di Carmichael è \(n=561\). Si tratta del più piccolo Carmichael noto ed è il prodotto di tre numeri primi:

\[ 561 = 3 \times 11 \times 17. \]

Nonostante \(561\) non sia primo, soddisfa comunque la proprietà di “pseudoprimo forte” in base a tutte le \(a\) coprime con \(561\), quindi  sembra primo nel test di primalità di Fermat \( a^{n-1} \equiv 1 \pmod{n}\).

\[a^{560} \equiv 1 \pmod{561}\]

Per verificarlo considero tutti i numeri coprimi con \( n = 561 \) ovvero quei numeri interi \( 1 < a < 561 \) che non hanno divisori in comune con 561, quindi il massimo comune divisore è 1.

$$ MCD(a,561) = 1 $$

I numeri coprimi con \( n=561 \) sono tutti i numeri che non sono multipli di 3, 11, 17 ossia dei fattori primi di 561.

$$ 2, 4, 5, 7, 8, 10, 13, 14, 16, 19, .... , 559, 560 $$

Tutti questi numeri \( a \) soddisfano la condizione \( MCD(a,560) = 1 \).

Ora verifico se sono anche pseudoprimi con 561. Per essere pseudoprimi devono soddisfare il teorema di Fermat \( a^{n-1} \equiv 1 \pmod{n} \)

Base	Test di Fermat	Base in cui 561 è Pseudoprimo
\( a = 2 \)	\( 2^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 4 \)	\( 4^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 5 \)	\( 5^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 7 \)	\( 7^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 10 \)	\( 10^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 13 \)	\( 13^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 14 \)	\( 14^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 16 \)	\( 16^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 19 \)	\( 19^{560} \equiv 1 \pmod{561} \)	✅ si
...	...	...
\( a = 559 \)	\( 559^{560} \equiv 1 \pmod{561} \)	✅ si
\( a = 560 \)	\( 560^{560} \equiv 1 \pmod{561} \)	✅ si

Questo conferma che tutti i numeri coprimi con \( n=561 \) sono anche pseudoprimi con \( n \).

Nota. Come si vedrà, c'è anche un altro metodo più rapido per verificare questa proprietà, senza dover controllare se ogni singolo numero soddisfa il teorema di Fermat. Basta verificare che il numero \( n \) sia composto da almeno tre fattori primi, non ripetuti, e che \( p_i-1 \) sia un divisore di \( n-1 \) per ogni fattore primo del numero \( n \).

Questo fa sì che \(561\) sia un falso positivo per il test di primalità basato su \(a^{n-1} \equiv 1 \pmod{n}\) (test di Fermat), e dunque rientri nella categoria dei numeri di Carmichael.

Per evitarli servono test di primalità più affidabili come il test di Miller-Rabin o quello di Baillie-PSW.

Il criterio di Korselt

Il criterio o teorema di Korselt mi permette di verificare se un intero è un numero di Carmichael senza dover verificare tutte le basi una a una.

Queste condizioni garantiscono che \( n \) soddisfi la proprietà \( a^{n-1} \equiv 1 \pmod{n} \) per tutti gli \( a \) coprimi con \( n \) senza doverli controllare uno a uno.

Esempio

Il primo numero di Carmichael è il \( 561 \).

Si tratta di un numero composto da tre fattori primi \( 561 = 3 \times 11 \times 17 \), nessuno dei quali è presente più di una volta nella fattorizzazione.

Verifico se per ogni fattore vale la condizione \( p_i - 1 \mid n - 1 \)

• Se \( p_i = 3  \rightarrow  2 \mid 560 \)
  Il numero 2 è un divisore di 560.
• Se \( p_i = 11  \rightarrow  10 \mid 560 \)
  Il numero 10 è un divisore di 560.
• Se \( p_i = 17  \rightarrow  16 \mid 560 \)
  Il numero 16 è un divisore di 560.

Dato che questa condizione è soddisfatta per tutti i fattori primi di \( 561 \), posso affermare che il numero è un numero di Carmichael.

Dimostrazione

Devo dimostrare che \(n\) è un numero di Carmichael se e solo se, per ogni fattore primo \(p\) di \(n\), vale \(p - 1 \mid n - 1\) cioè \(p - 1\) divide \(n - 1\).

So già che \(n\) è un numero di Carmichael se è composto da fattori primi distinti tra loro:

\[ n = p_1 \cdot p_2 \cdots p_h \]

Dove \(p_1, p_2, \dots, p_h\) sono i fattori primi di \(n\).

Inoltre, per definizione \(n\) è un numero di Carmichael se, per ogni intero \(a\) coprimo con \( n \) ossia tale che \(\gcd(a, n) = 1\), è soddisfatto il Teorema di Fermat:

\[ a^{n-1} \equiv 1 \pmod{n} \]

Ora, prendo un intero \(a\) qualsiasi tale che \(\gcd(a, n) = 1\) ossia coprimo con \( n \).

Dato che \(a\) è coprimo con \(n\), è anche coprimo con ciascun fattore primo \(p_i\) di \(n\).

Quindi, sempre per il Piccolo Teorema di Fermat, deduco che per ciascun fattore primo vale la seguente congruenza:

\[ a^{p_i - 1} \equiv 1 \pmod{p_i} \]

Per l'ipotesi iniziale \(p_i - 1\) divide \(n - 1\).

$$ p - 1 \mid n - 1 $$

Quindi, esiste un intero \(k_i\) tale che:

\[ n - 1 = k_i \cdot (p_i - 1) \]

Usio questa relazione per riscrivere \(a^{n-1}\):

\[ a^{n-1} = a^{k_i \cdot (p_i - 1)} = \left(a^{p_i - 1}\right)^{k_i} \]

Poiché \(a^{p_i - 1} \equiv 1 \pmod{p_i}\) segue che:

\[ \left(a^{p_i - 1}\right)^{k_i} \equiv 1^{k_i} \equiv 1 \pmod{p_i} \]

Quindi, sostituendo \( a^{n-1} = \left(a^{p_i - 1}\right)^{k_i} \) , per ogni fattore primo \( p_i \) del numero \( n \) vale:

\[ a^{n-1} \equiv 1 \pmod{p_i}, \quad \text{per ogni } p_i \]

Poiché \(n = p_1 \cdot p_2 \cdots p_h\) è il prodotto di fattori primi distinti, posso combinare le congruenze \(a^{n-1} \equiv 1 \pmod{p_i}\) per tutti \(i = 1, 2, \dots, h\) usando il Teorema Cinese del Resto.

\[
\begin{cases}
a^{n-1} \equiv 1 \pmod{p_1}, \\
a^{n-1} \equiv 1 \pmod{p_2}, \\
\vdots \\
a^{n-1} \equiv 1 \pmod{p_h}.
\end{cases}
\]

Il Teorema Cinese del Resto afferma che, poiché i moduli \(p_1, p_2, \dots, p_h\) sono coprimi (tutti primi e distinti), le congruenze sopra si possono combinare in un'unica congruenza modulo \(n = p_1 \cdot p_2 \cdots p_h\).

In questo caso, poiché il lato destro di ogni congruenza è uguale a \(1\), ottengo:

\[ a^{n-1} \equiv 1 \pmod{p_1 \cdot p_2 \cdots p_h} \]

\[ a^{n-1} \equiv 1 \pmod{n} \]

Ho così dimostrato che, se \(p_i - 1 \mid n - 1\) per ogni fattore primo \(p_i\) di \(n\), allora \(n\) è un numero di Carmichael, perché soddisfa \(a^{n-1} \equiv 1 \pmod{n}\) per ogni \(a\) coprimo con \(n\).

Note

Alcune note aggiuntive sui numeri di Carmichael

• Tutti i numeri di Carmichael sono dispari
  Questa conclusione deriva dal teorema di Korselt, secondo cui \( p-1 \) deve dividere \( n-1 \) per ogni fattore primo \( p \) di \( n \). Se \( n \) fosse pari e contenesse un fattore primo dispari \( p \), allora \( p-1 \) sarebbe pari e non potrebbe dividere \( n-1 \), che è dispari. Di conseguenza, affinché la condizione di Korselt sia soddisfatta, tutti i numeri di Carmichael devono essere dispari.
• Numeri di Carmichael e numeri di Mersenne
  C’è una strana connessione tra i numeri di Carmichael e i numeri primi di Mersenne (del tipo \( 2^p - 1 \)), anche se è più una curiosità che una regola precisa. Ci sono numeri di Carmichael che hanno nella loro fattorizzazione dei primi che compaiono nella fattorizzazione dei numeri di Mersenne ma non è una regola fissa.

  Nota. Questa occorrenza è un fenomeno sporadico e non riflette una relazione diretta o sistematica tra le due famiglie di numeri. Matematicamente parlando, Carmichael e Mersenne sono due mondi diversi: uno parla di numeri che sembrano primi ma non lo sono, l’altro di numeri che potrebbero essere primi ma non sempre lo sono.

• I numeri di Carmichael hanno almeno tre fattori primi
  Un numero di Carmichael non può essere composto da due fattori primi, ne ha almeno tre o più.

  Dimostrazione. Supponiamo per assurdo che \( n \) sia un numero di Carmichael composto da soli due fattori primi distinti \( p \) e \( q \), cioè \( n = p \cdot q \) dove \( p \) e \( q \) sono primi distinti. Poiché \( n \) è un numero di Carmichael, deduco per definizione che \( p-1 \) e \( q-1 \) siano divisori di \( n-1 \). $$ p - 1 \mid n - 1 $$ $$ q - 1 \mid n - 1 $$ Essendo divisori, le divisioni \( \frac{n-1}{p-1} \) e \( \frac{n-1}{q-1} \) non producono un resto.  \[ n - 1 \equiv 0 \pmod{p - 1} \] \[  n - 1 \equiv 0 \pmod{q - 1} \] Inoltre, posso riscrivere \( n - 1 \) aggiungendo e sottraendo \( p \) come: \[ n - 1 = p \cdot q - 1 \] \[ n-1= p \cdot q - 1 + p - p \] \[ n-1=  p(q - 1) + (p - 1) \] Sapendo che \[  n - 1 \equiv 0 \pmod{q - 1} \] Sostituisco \( n-1 \) \[ p(q - 1) + (p - 1) \equiv 0 \pmod{q - 1} \] Poiché \( q-1 \) è divisibile per il modulo \( q-1 \), il resto è zero. Quindi, la congruenza si semplifica: \[ p - 1 \equiv 0 \pmod{q - 1} \] Questo significa che \( q-1 \) è un divisore di \( p-1 \) e quest'ultimo è un multiplo.  \[ p - 1 \text{ è un multiplo di } q - 1, \quad \text{cioè } p - 1 \geq q - 1 \] Allo stesso modo, scambiando i ruoli di \( p \) e \( q \), si ottiene: \[ n - 1 = p \cdot q - 1 \] \[ n-1= p \cdot q - 1 + q - q \] \[ n-1=  q(p - 1) + (q - 1) \] Sapendo che \[ n - 1 \equiv 0 \pmod{p - 1} \] \[ q(p - 1) + (q - 1) \equiv 0 \pmod{p - 1} \] \[  (q - 1) \equiv 0 \pmod{p - 1} \] Quindi \( p-1 \) è un divisore di \( q-1 \) e quest'ultimo è un multiplo.   \[ q - 1 \text{ è un multiplo di } p - 1, \quad \text{cioè } q - 1 \geq p - 1 \] Dalle due disuguaglianze \( p - 1 \geq q - 1 \) e \( q - 1 \geq p - 1 \), segue che: \[ p - 1 = q - 1 \] Quindi: \[ p = q \] il che contraddice l'ipotesi che \( p \) e \( q \) siano primi distinti. L'ipotesi che un numero di Carmichael possa essere composto da due soli fattori primi distinti porta a una contraddizione. Di conseguenza, un numero di Carmichael deve essere composto da almeno tre fattori primi distinti.

E così via.