Numero di Carmichael

In teoria dei numeri, un numero di Carmichael è un intero positivo composto n che soddisfa la congruenza

${\displaystyle b^{n-1}\equiv 1\mod n}$

per tutti gli interi b che sono coprimi con n o, equivalentemente, che verificano la congruenza

${\displaystyle 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 ${\displaystyle 2^{341}\equiv 2\mod 341}$, ma 341 non è primo, essendo il prodotto di 11 e 31. Un numero tale che ${\displaystyle 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[1]:

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[2]:

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).[3] 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 ${\displaystyle \varepsilon >0}$ esista un valore ${\displaystyle x_{0}(\varepsilon )}$ tale che, detto C(x) il numero dei numeri di Carmichael minori o uguali a x,

${\displaystyle C(x)>x^{1-\varepsilon }}$

per ogni ${\displaystyle x\geq x_{0}(\varepsilon )}$.[4] Nel 1994 W. R. (Red) Alford, Andrew Granville e Carl Pomerance provarono l'infinità dei numeri di Carmichael, dimostrando che, per x sufficientemente grande, ${\displaystyle C(x)>x^{2/7}}$.[5] Glyn Harman ha successivamente migliorato questo risultato provando che ${\displaystyle C(x)>x^{0.332}}$ per x sufficientemente grande,[6] e poi portando l'esponente a 1/3[7].

Una stima dall'alto della funzione C(x) fu fornita dallo stesso Erdős, che dimostrò nel 1956 che

${\displaystyle 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 è:[3].

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
${\displaystyle 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 ${\displaystyle X=10^{n}}$ con n crescente:

${\displaystyle 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.[8]

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.

Note

1. (EN) Sequenza A002997, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
2. (EN) Sequenza A006931, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
3. Richard Pinch, "The Carmichael numbers up to 10^18", aprile 2006 (estendendo un lavoro precedente Copia archiviata (ps), su chalcedon.demon.co.uk. URL consultato il 22 aprile 2007 (archiviato dall'url originale il 1º marzo 2007).[1][2]).
4. Richard Crandall e Carl Pomerance, Prime numbers. A computational perspective, seconda, Springer, 2005, pp. 133-135, ISBN 0-387-25282-7.
5. W. R. Alford, A. Granville, e C. Pomerance. "There are Infinitely Many Carmichael Numbers." Annals of Mathematics 139 (1994) 703-722.
6. Glyn Harman. "On the number of Carmichael numbers up to X." Bull. Lond. Math. Soc. 37 (2005) 641-650.
7. Glyn Harman. "Watt's mean value theorem and Carmichael numbers." International Journal of Number Theory 4 (2008), n. 2, 241--248.
8. Everett W. Howe. "Higher-order Carmichael numbers." Mathematics of Computation 69 (2000), pp. 1711–1719.

Bibliografia

• Chernick, J. (1935). On Fermat's simple theorem. Bull. Amer. Math. Soc. 45, 269–274.
• Ribenboim, Paulo (1996). The New Book of Prime Number Records.
• Löh, Günter and Niebuhr, Wolfgang (1996). A new algorithm for constructing large Carmichael numbers(pdf)
• Korselt (1899). Probleme chinois. L'intermediaire des mathematiciens, 6, 142–143.
• Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence a^P-1 ≡ 1 (mod P). Am. Math. Month. 19 22–27.
• Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.

Voci correlate

• Piccolo teorema di Fermat
• Pseudoprimo di Fermat
• Numero di Mersenne
• Funzione di Carmichael
• Teorema di Carmichael

Altri progetti

Altri progetti

• Wikibooks

• Wikibooks contiene una tavola di numeri di Carmichael

Collegamenti esterni

• Mathpages: The Dullness of 1729, su mathpages.com. URL consultato il 22 aprile 2007 (archiviato dall'url originale il 30 settembre 2007).
• Carmichael number^[collegamento interrotto] - su MathWorld
• Final Answers Modular Arithmetic, su numericana.com.