Don't take life too seriously: it's just a temporary situation

Carmichael (numeri di)

Teoria dei numeri 

Indice

  1. 1. Pagina principale
  2. 2. Distribuzione dei numeri di Carmichael

I numeri di Carmichael sono pseudoprimi di Fermat in qualsiasi base, cioè sono numeri composti n tali che bn – 1 ≡ 1 mod n per ogni b primo rispetto a n.

 

Nel 1885 il matematico ceco Václav Šimerka aveva trovato i primi 7, ma il suo lavoro passò inosservato.

Furono poi studiati nel 1899 da A. Korselt, che ne stabilì alcune proprietà, ma non ne trovò nessun altro.

Il termine venne coniato da N.G.W.H. Beeger in onore di Robert Carmichael (Goodwater, USA, 1/3/1879 – Merriam, USA, 2/5/1967), che li studiò approfonditamente tra il 1909 e il 1912, trovandone 15, tra i quali il minimo esempio, 561, e avanzò la congettura che siano infiniti.

 

D. Mahnke dimostrò nel 1912 che anche 1105, 1729, 2465 e 10585 sono numeri di Carmichael.

 

Da allora una comprensione sempre migliore delle loro proprietà portò a individuarne sempre di più.

 

Un numero naturale n è un numero di Carmichael se e solo se è il prodotto di tre o più primi dispari distinti e per ogni primo p che divide n, p – 1 divide n – 1 (criterio di Korselt), pertanto un numero di Carmichael non è mai multiplo di un quadrato.

Un criterio equivalente è che un numero naturale è un numero di Carmichael se e solo se λ(n) divide n – 1, dove λ(n) è la funzione di Carmichael (Carmichael, 1910), ossia se n è il prodotto dei primi p1, p2, p3, … pk, mcm(p1 – 1, p2 – 1, p3 – 1, … pk – 1) divide n – 1.

 

Un numero naturale composto dispari non multiplo di quadrati è un numero di Carmichael se e solo se divide il denominatore di Bn – 1.

 

I fattori primi di un numero di Carmichael sono minori della sua radice quadrata.

 

I 43 numeri di Carmichael inferiori a un milione sono: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633.

 

Qui trovate i numeri di Carmichael inferiori a 1012.

 

Se 6k + 1, 12k + 1 e 18k + 1 sono tre numeri primi, il loro prodotto è un numero di Carmichael (J. Chernik, 1939). Si ottengono in questo modo molti numeri di Carmichael; i primi sono: 1729 (per k = 1), 294409 (per k = 6), 56052361, (per k = 35) v. numeri di Zeisel.

Il metodo di Chernik non è che un caso particolare di un metodo generale per trovare numeri di Carmichael che siano il prodotto di tre primi: se n = pqr, p = ad + 1, q = bd + 1 e r = cd + 1 sono primi dispari distinti, con d = MCD(p – 1, q – 1, r – 1) e abcd divide n – 1, allora n è un numero di Carmichael.

Un numero della forma Formula per i numeri di Carmichael, con k multiplo di 2n – 4, n maggiore di 3 e gli n fattori del prodotto tutti primi, è un numeri di Carmichael. Per esempio, per n = 4 e k = 8976 si ottiene 302869127073192147073, mentre per n = 5 e k = 10920 si ottiene 521635331852681575100906881.

 

Analogamente se k + 1, 2k + 1, 4k + 1, 7k + 1 e 14k + 1 sono primi e k è un multiplo di 28, (k + 1)(2k + 1)(4k + 1)(7k + 1)(14k + 1) è un numero di Carmichael; il minimo esempio, per k = 28 • 2136, è 599966117492747584686619009.

Più in generale, se a1k + 1, a2k + 1, ... ank + 1, sono primi e k è un multiplo di a1a2 ... an, il prodotto (a1k + 1)(a2k + 1) ... (ank + 1) è un numero di Carmichael.

Per esempio, (k + 1)(2k + 1)(4k + 1)(8k + 1)(16k + 1)(31k + 1)(62k + 1)(124k + 1)(248k + 1) è un numero di Carmichael se i fattori sono primi e k è un multiplo di 496. Il minimo numero di Carmichael di questa forma si ottiene per k = 6693159943680 e ha 127 cifre.

Da un numero di Carmichael multiplo di k primi p1, p2, … pk se ne possono ricavare altri della forma q1q2qk, con qr = 1 + m(pr – 1), se m ≡ 1 mod mcm(p1 – 1, p2 – 1,… pk – 1) e i vari qr sono tutti primi (Andrew Granville e Carl Pomerance, 2001).

 

 

Varianti di questi metodi hanno permesso di trovare numeri di Carmichael enormi e con un gran numero di fattori primi:

  • nel 1996 Günther Loh e Wolfgang Niebuhr costruirono un numero di Carmichael, prodotto di 1101518 fattori primi, di 16142049 cifre;

  • nel 2003 W.R. Alford e Jon Grantham ne costruirono uno con 19565300 fattori primi;

  • nell’ottobre 2011 Steven Hayman e Andrew Shallue ne costruirono uno con 1021449117 fattori primi;

  • un mese dopo gli stessi matematici ne costruirono uno di 295 miliardi di cifre, con 10333229505 fattori primi.

Si conoscono numeri di Carmichael con esattamente n fattori primi per tutti i valori di n da 3 a 19565220 (W.R. Alford e Jon Grantham, 2003).

Dati n primi p1, p2, … pn, con pr = 1 + m2n + r – 2(2n – 1), il loro prodotto è un numero di Carmichael con esattamente n fattori primi (Andrew Granville e Carl Pomerance, 2001).

 

Non è stato dimostrato che alcuna delle formule riportate produca infiniti numeri di Carmichael, perché non è stato dimostrato che esistano infiniti insiemi di primi che soddisfino le varie condizioni, tuttavia se la congettura di Dickson fosse vera, ciascuna di queste formule produrrebbe infiniti numeri di Carmichael.

 

Viceversa è stato dimostrato che i numeri di Carmichael di alcune forme particolari sono in numero finito o addirittura non esistono:

  • l’unico della forma 15pq, con p e q primi, è 62745;

  • se p e q sono primi dispari e q = kp + 1, non esistono numeri di Carmichael multipli di pq; in particolare non ne esistono multipli di 21 o 39;

  • non esistono numeri di Carmichael della forma 2n + 1 (Thomas Wright);

  • non esistono numeri di Carmichael che siano il prodotto di primi di Fermat (Thomas Wright).

 

Thomas Wright dimostrò che se n è un numero di Carmichael prodotto dei primi p1, p2, p3, … pk e mcm(p1 – 1, p2 – 1, p3 – 1, … pk – 1) = 2kq con q primo, n è multiplo di almeno due primi di Fermat e

  • q non è della forma 12m + 1;

  • se q è della forma 3k + 2, n è multiplo di 5 se e solo se q è della forma 4m + 3;

  • se non esistono altri primi di Fermat oltre ai cinque noti, q è 3, 5, 7 o 127 e n è uno dei seguenti numeri:

    • 561 = 3 • 11 • 17;

    • 1105 = 5 • 13 • 17;

    • 2465 = 5 • 17 • 29;

    • 278545 = 5 • 17 • 29 • 113;

    • 3224065 = 5 • 13 • 193 • 257;

    • 11119105 = 5 • 17 • 257 • 509;

    • 2479305985 = 5 • 13 • 193 • 257 • 769;

    • 123155771490305 = 5 • 29 • 113 • 65537 • 114689.

 

W.R. Alford e J. Grantham costruirono un numero di Carmichael con 125458 fattori primi che è multiplo di almeno un numero di Carmichael con n fattori primi, per n da 50 a 125000.

 

Nel 1995 J.M. Borwein e E. Wong dimostrarono che un intero n > 2 non multiplo di quadrati è un numero di Carmichael se e solo se Congruenza dimostrata da Borwein e Wong.

 

Se un intero n è il prodotto di s primi p1, p2, … ps, valgono le s congruenze Congruenza dimostrata da Meštrović per tutti gli s fattori primi pm di n (Romeo Meštrović, 2013).

 

Un numero di Carmichael può essere pseudoprimo di Eulero – Jacobi o pseudoprimo forte di Fermat in molte basi, ma non in tutte; può invece essere pseudoprimo di Eulero (I) in ogni base (esclusi i suoi divisori), ossia pseudoprimo assoluto di Eulero.

 

Tutti i divisori dei numeri di Carmichael sono numeri ciclici (II).

 

Nel 1977 Hugh C. Williams chiese se esistano numeri di Carmichael n con un numero dispari di fattori primi che siano anche numeri di Lucas – Carmichael, ossia tali che per ogni fattore primo p di n, p + 1 divida n + 1. Non se ne conosce nessuno; se esistono sono maggiori di 1016 (Richard G.E. Pinch, 2007).

 

La conguenza (a + b)nan + bn mod n vale se e solo se n è primo o un numero di Carmichael (Pratibha Ghatage e Brian Scott, 2005).

Bibliografia

  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.