title: Numero di Carmichael
text: # Numero di Carmichael
  
  In teoria dei numeri, un numero di Carmichael è un intero positivo composto n che soddisfa la congruenza
  
      $b^{n-1}\equiv 1\mod n$
  
  per tutti gli interi b che sono coprimi con n o, equivalentemente, che verificano la congruenza
  
      $b^{n}\equiv b\mod n$
  
  per ogni b. Prendono il nome da Robert Carmichael, che ne trovò i primi esempi.
  
  Il piccolo teorema di Fermat afferma che tutti i numeri primi hanno quella proprietà, ma il viceversa non è vero: ad esempio $2^{341}\equiv 2\mod 341$, ma 341 non è primo, essendo il prodotto di 11 e 31. Un numero tale che $b^{n}\equiv b\mod n$ è detto pseudoprimo di Fermat rispetto alla base b; i numeri di Carmichael sono pseudoprimi di Fermat in ogni base, cioè assoluti.
  
  I numeri di Carmichael rivestono un'importanza notevole perché passano in ogni caso il test di primalità di Fermat pur essendo composti: la loro esistenza impedisce di utilizzare questo test per certificare con sicurezza la primalità di un numero, mentre rimane utilizzabile per dimostrare che un numero è composto.
  
  ## Proprietà
  
  Una caratterizzazione dei numeri di Carmichael è stata fornita nel 1899 da Korselt: un intero positivo composto n è un numero di Carmichael se e solo se è privo di quadrati e, per ogni divisore primo p di n, p-1 divide n-1.
  
  Un corollario di questo teorema è che tutti i numeri di Carmichael sono dispari: se infatti n fosse pari con un fattore primo p dispari, si dovrebbe avere p-1|n-1 (a|b significa a divide b), ma p-1 sarebbe pari al contrario di n-1, dispari, e quindi p-1 non lo potrebbe dividere.
  
  Korselt, pur dimostrando questa proprietà, non riuscì a trovarne un esempio; nel 1910 Robert Daniel Carmichael trovò il più piccolo numero con questa proprietà, 561, legando così il suo nome a questi numeri.
  
  Si può verificare facilmente che 561 è un numero di Carmichael con il teorema di Korselt. Infatti, 561 = 3 · 11 · 17 è privo di quadrati e 2|560, 10|560 e 16|560. I numeri di Carmichael successivi sono:
  
      1105 (5 · 13 · 17), 1729 (7 · 13 · 19), 2465 (5 · 17 · 29), 2821 (7 · 13 · 31), 6601 (7 · 23 · 41), 8911 (7 · 19 · 67)
  
  I numeri di Carmichael hanno almeno tre divisori primi positivi. I primi numeri di Carmichael con k = 3, 4, 5,... fattori primi sono:
  
  | k | |
  | - | - |
  | 3 | 561 = 3 · 11 · 17 |
  | 4 | 41041 = 7 · 11 · 13 · 41 |
  | 5 | 825265 = 5 · 7 · 17 · 19 · 73 |
  | 6 | 321197185 = 5 · 19 · 23 · 29 · 37 · 137 |
  | 7 | 5394826801 = 7 · 13 · 17 · 23 · 31 · 67 · 73 |
  | 8 | 232250619601 = 7 · 11 · 13 · 17 · 31 · 37 · 73 · 163 |
  | 9 | 9746347772161 = 7 · 11 · 13 · 17 · 19 · 31 · 37 · 41 · 641 |
  
  Curiosamente, il primo numero di Carmichael (561) si può esprimere come somma di due potenze di primo grado in un numero di modi maggiore rispetto ad ogni numero più piccolo (sebbene ciò sia banalmente vero per ogni intero positivo), il secondo numero di Carmichael (1105) si può scrivere come somma di due quadrati in più maniere rispetto a ogni numero più piccolo, e il terzo numero di Carmichael (1729) è il numero di Hardy-Ramanujan: il più piccolo numero che si può scrivere come somma di due cubi in due modi diversi.
  
  ## Distribuzione
  
  I numeri di Carmichael sono rari: ad esempio, ci sono 1.401.644 numeri di Carmichael compresi fra 1 e $10^{18}$ (circa uno ogni 700 miliardi di numeri). Ciò rende i test di primalità basati sul piccolo teorema di Fermat un po' più incerti rispetto ad altri, come il test di primalità di Solovay-Strassen.
  
  J. Chernick dimostrò nel 1939 che se i numeri 6k+1, 12k+1 e 18k+1 sono primi, allora il loro prodotto è un numero di Carmichael; non è noto però se i numeri in questa forma siano finiti o infiniti.
  
  Paul Erdős mostrò, con ragioni euristiche, che dovrebbero esistere infiniti numeri di Carmichael, e congetturò che per ogni $\varepsilon >0$ esista un valore $x_{0}(\varepsilon )$ tale che, detto C(x) il numero dei numeri di Carmichael minori o uguali a x,
  
      $C(x)>x^{1-\varepsilon }$
  
  per ogni $x\geq x_{0}(\varepsilon )$. Nel 1994 W. R. (Red) Alford, Andrew Granville e Carl Pomerance provarono l'infinità dei numeri di Carmichael, dimostrando che, per x sufficientemente grande, $C(x)>x^{2/7}$. Glyn Harman ha successivamente migliorato questo risultato provando che $C(x)>x^{0.332}$ per x sufficientemente grande, e poi portando l'esponente a 1/3.
  
  Una stima dall'alto della funzione C(x) fu fornita dallo stesso Erdős, che dimostrò nel 1956 che
  
  $C(x)<x\exp {\frac {-k\log x\log \log \log x}{\log \log x}}$
  
  per qualche costante k.
  
  La distribuzione dei numeri di Carmichael minori delle potenze di 10 è:.
  
  | $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
  | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
  | $C(10^{n})$ | 0 | 0 | 1 | 7 | 16 | 43 | 105 | 255 | 646 | 1547 | 3605 | 8241 | 19279 | 44706 | 105212 | 246683 | 585355 | 1401644 | 3381806 | 8220777 | 20138200 |
  
  La tabella sottostante mostra gli approssimati valori per la costante k per il limite massimo dato da Erdős per $X=10^{n}$ con n crescente:
  
  | $n$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
  | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
  | k | 2.93319 | 2.19547 | 2.07632 | 1.97946 | 1.93388 | 1.90495 | 1.87989 | 1.86870 | 1.86421 | 1.86377 | 1.8624 | 1.86293 | 1.86301 | 1.86406 | 1.86472 | 1.86522 | 1.86565 | 1.86598 | 1.86619 |
  
  Löh e Niebuhr trovarono nel 1992 alcuni numeri di Carmichael di grandi dimensioni, tra cui uno con 1.101.518 fattori e oltre 16 milioni di cifre.
  
  ## Numeri di Carmichael di ordine superiore
  
  I numeri di Carmichael si possono generalizzare utilizzando gli strumenti dell'algebra astratta.
  
  La definizione data afferma che un intero composto n è di Carmichael esattamente quando la funzione potenza n-esima $p_n$ dall'anello $Z_n$ degli interi modulo n in sé è la funzione identica. L'identità è l'unico endomorfismo da una $Z_n-algebra$ in $Z_n,$ pertanto si può riscrivere la definizione richiedendo che $p_n$ sia un endomorfismo su $Z_n.$ Come prima, $p_n$ soddisfa la stessa proprietà se n è primo.
  
  La funzione potenza n-esima $p_n$ è definita in ogni $Z_n-algebra$ A. Un teorema afferma che n è primo se e solo se tutte queste funzioni $p_n$ sono endomorfismi.
  
  A cavallo fra queste due condizioni vi è la definizione di numero di Carmichael di ordine m, per un intero positivo m, come un numero composto n tale che $p_n$ è un endomorfismo su ogni $Z_n-algebra$ che può si può generare come $Z_n-modulo$ da m elementi. I numeri di Carmichael di ordine 1 sono gli ordinari numeri di Carmichael.
  
  ### Proprietà
  
  Il criterio di Korselt si può generalizzare ai numeri di Carmichael di ordine superiore, come mostrato da Howe.
  
  Nella stessa pubblicazione, vengono suggerite delle ragioni euristiche, secondo cui ci sono infiniti numeri di Carmichael di ordine m, per ogni m. Tuttavia, non è noto nessun numero di Carmichael di ordine 3 o superiore.
  
  