Numero di Carmichael

Da Wikipedia, l'enciclopedia libera.

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à[modifica | modifica sorgente]

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[modifica | modifica sorgente]

I numeri di Carmichael sono rari: ad esempio, ci sono 1.401.644 numeri di Carmichael compresi fra 1 e 1018 (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 \varepsilon>0 esista un valore x_0(\varepsilon) tale che, detto C(x) dei numeri di Carmichael minori o uguali a x,

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

per ogni 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 n sufficientemente grande, C(x)>x^{2/7}.[5] Glyn Harman ha successivamente migliorato questo risultato provando che 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

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 al di sotto delle potenze di 10 è:[3].

n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
C(10n) 1 7 16 43 105 255 646 1547 3605 8241 19279 44706 105212 246683 585355 1401644 3381806 8220777

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[modifica | modifica sorgente]

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 pn dall'anello Zn degli interi modulo n in sé è la funzione identica. L'identità è l'unico endomorfismo da una Zn-algebra in Zn, pertanto si può riscrivere la definizione richiedendo che pn sia un endomorfismo su Zn. Come prima, pn soddisfa la stessa proprietà se n è primo.

La funzione potenza n-esima pn è definita in ogni Zn-algebra A. Un teorema afferma che n è primo se e solo se tutte queste funzioni pn 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 pn è un endomorfismo su ogni Zn-algebra che può si può generare come Zn-modulo da m elementi. I numeri di Carmichael di ordine 1 sono gli ordinari numeri di Carmichael.

Proprietà[modifica | modifica sorgente]

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[modifica | modifica sorgente]

  1. ^ (EN) Sequenza A002997 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  2. ^ (EN) Sequenza A006931 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  3. ^ a b Richard Pinch, "The Carmichael numbers up to 1018", aprile 2006 (estendendo un lavoro precedente [1][2][3]).
  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[modifica | modifica sorgente]

  • 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 aP-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[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica