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

Carmichael (numeri di)

Teoria dei numeri 

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.

Prendono il nome da Robert Carmichael, 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 mcm(p1 – 1, p2 – 1, p3 – 1, … pk – 1) divide n – 1, se n è il prodotto dei primi p1, p2, p3, … pk.

 

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

 

I 43 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, Andrew Granville e Carl Pomerance dimostrarono nel 1993 che i numeri di Carmichael sono infiniti e che ve ne sono almeno nα minori di n, dove Due settimi. Nel 2005 G. Harman portò l’esponente a un valore lievemente superiore a Un terzo, quindi i numeri di Carmichael inferiori a n sono più di Radice cubica di n.

 

K. Matomäki dimostrò che ogni progressione aritmetica del tipo am + b, con a e b primi tra loro e b residuo quadratico di a, contiene almeno Radice quinta di n numeri di Carmichael inferiori a n, per n abbastanza grande.

 

Nel 2012 T. Wright dimostrò che dati due interi positivi a e b primi fra loro, vi sono almeno n^(k / log3(n)^2) numeri di Carmichael della forma am + b inferiori a n, per una costante k.

Erdös dimostrò invece nel 1956 che i numeri di Carmichael inferiori a n non superano Formula per il massimo numero di numeri di Carmichael inferiori a n, con k costante. Pomerance, Sefridge e Wagstaff dimostrarono nel 1980 che asintoticamente k è almeno 1.

 

I numeri di Carmichael minori di n con esattamente 3 fattori primi sono al massimo Formula per il massimo numero di numeri di Carmichael inferiori a n con esattamente tre fattori primi (Damgård, Landrock e Pomerance, 1993).

In particolare, se un numero di Carmichael ha 3 fattori primi, il minimo dei quali è p, gli altri due non sono superiori a Formula per il massimo dei fattori primi di un numero di Carmichael con esattamente tre fattori primi (R. Pinch e C. Nash, 2001) e il minore dei due è inferiore a 2p2 – 2p + 1.

In generale, vi è solo un numero finito di numeri di Carmichael con k fattori primi, una volta fissati i primi k – 2.

 

Nel 1990 G.Jaeschke calcolò tutti i numeri di Carmichael sino a 1012. Altri in seguito estesero la tabella fino a 1021 (R.G.E. Pinch).

 

La tabella seguente mostra il numero di numeri di Carmichael minori di alcune potenze di 10.

n

Numeri di Carmichael minori di n

10

0

102

0

103

1

104

7

105

16

106

43

107

105

108

255

109

646

1010

1547

1011

3605

1012

8241

1013

19279

1014

44706

1015

105212

1016

246683

1017

585355

1018

1401644

1019

3381806

1020

8220777

1021

20138200

 

Non è noto se esistano infiniti numeri di Carmichael con un numero fissato di fattori primi, né se ne esistano con un numero di fattori primi arbitrariamente grande. I numeri di Carmichael con esattamente 3 fattori primi, il minimo dei quali fissato, sono in numero finito; non è noto se valga la stessa proprietà per quelli con 4 o più fattori.

 

La tabella seguente mostra i minimi numeri di Carmichael per alcuni numeri di fattori primi.

Numero di fattori

Minimo numero di Carmichael

3

541 = 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

10

1436697831295441 = 11 • 13 • 19 • 29 • 31 • 37 • 41 • 43 • 71 • 127

11

60977817398996785 = 5 • 7 • 17 • 19 • 23 • 37 • 53 • 73 • 79 • 89 • 233

12

7156857700403137441 = 11 • 13 • 17 • 19 • 29 • 37 • 41 • 43 • 61 • 97 • 109 • 127

13

1791562810662585767521 = 11 • 13 • 17 • 19 • 31 • 37 • 43 • 71 • 73 • 97 • 109 • 113 • 127

14

87674969936234821377601 = 7 • 13 • 17 • 19 • 23 • 31 • 37 • 41 • 61 • 67 • 89 • 163 • 193 • 241

15

6553130926752006031481761 = 11 • 13 • 17 • 19 • 29 • 31 • 41 • 43 • 61 • 71 • 73 • 109 • 113 • 127 • 181

16

1590231231043178376951698401 = 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 71 • 73 • 79 • 97 • 113 • 199

17

35237869211718889547310642241 = 13 • 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 71 • 73 • 97 • 113 • 127 • 211

18

32809426840359564991177172754241 = 13 • 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 71 • 73 • 97 • 127 • 199 • 281 • 397

19

2810864562635368426005268142616001 = 13 • 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 71 • 73 • 109 • 113 • 127 • 151 • 281 • 353

20

349407515342287435050603204719587201 = 11 • 13 • 17 • 19 • 29 • 31 • 37 • 41 • 43 • 61 • 71 • 73 • 97 • 101 • 109 • 113 • 151 • 181 • 193 • 641

21

125861887849639969847638681038680787361 = 13 • 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 71 • 73 • 89 • 97 • 113 • 181 • 211 • 241 • 331 • 353

22

12758106140074522771498516740500829830401 = 13 • 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 71 • 73 • 89 • 97 • 101 • 113 • 127 • 181 • 193 • 211 • 1153

23

2333379336546216408131111533710540349903201 = 11 • 13 • 17 • 19 • 29 • 31 • 37 • 41 • 43 • 47 • 61 • 71 • 73 • 101 • 109 • 113 • 127 • 139 • 163 • 211 • 337 • 421 • 541

24

294571791067375389885907239089503408618560001 = 11 • 13 • 17 • 19 • 31 • 37 • 41 • 43 • 47 • 59 • 61 • 71 • 73 • 97 • 101 • 109 • 113 • 127 • 151 • 181 • 211 • 251 • 257 • 631

25

130912961974316767723865201454187955056178415601 = 11 • 13 • 17 • 19 • 29 • 31 • 37 • 41 • 43 • 47 • 61 • 71 • 73 • 101 • 109 • 113 • 127 • 139 • 151 • 181 • 211 • 241 • 281 • 541 • 701

26

13513093081489380840188651246675032067011140079201 = 11 • 17 • 19 • 29 • 31 • 37 • 41 • 43 • 47 • 53 • 61 • 71 • 73 • 79 • 97 • 101 • 109 • 127 • 151 • 157 • 163 • 179 • 271 • 281 • 337 • 433

27

7482895937713262392883306949172917048928068129206401 = 13 • 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 71 • 73 • 89 • 97 • 101 • 109 • 113 • 127 • 151 • 199 • 211 • 271 • 331 • 337 • 397 • 601

28

1320340354477450170682291329830138947225695029536281601 = 13 • 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 61 • 67 • 73 • 89 • 97 • 101 • 109 • 113 • 127 • 151 • 181 • 193 • 199 • 211 • 241 • 257 • 281 • 331 • 449

29

379382381447399527322618466130154668512652910714224209601 = 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 53 • 61 • 67 • 71 • 73 • 79 • 89 • 97 • 101 • 113 • 127 • 131 • 151 • 157 • 181 • 193 • 271 • 281 • 401 • 433 • 547

30

70416887142533176417390411931483993124120785701395296424001 = 11 • 17 • 19 • 29 • 31 • 37 • 41 • 43 • 47 • 53 • 61 • 71 • 73 • 79 • 97 • 101 • 109 • 113 • 127 • 131 • 139 • 157 • 163 • 167 • 241 • 313 • 449 • 461 • 487 • 599

31

2884167509593581480205474627684686008624483147814647841436801 = 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 53 • 61 • 67 • 71 • 73 • 79 • 89 • 97 • 101 • 109 • 113 • 127 • 131 • 151 • 157 • 163 • 181 • 199 • 211 • 241 • 271 • 353 • 617

32

4754868377601046732119933839981363081972014948522510826417784001 = 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 51 • 61 • 67 • 71 • 73 • 79 • 89 • 97 • 101 • 109 • 127 • 131 • 151 • 157 • 181 • 193 • 199 • 211 • 241 • 271 • 313 • 331 • 353 • 937

33

1334733877147062382486934807105197899496002201113849920496510541601 = 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 53 • 61 • 67 • 71 • 73 • 79 • 89 • 97 • 101 • 109 • 113 • 127 • 131 • 151 • 157 • 163 • 181 • 211 • 271 • 313 • 331 • 337 • 379 • 401 • 911

34

260849323075371835669784094383812120359260783810157225730623388382401 = 17 • 19 • 29 • 31 • 37 • 41 • 43 • 47 • 53 • 61 • 67 • 71 • 73 • 79 • 89 • 97 • 101 • 109 • 113 • 127 • 131 • 139 • 151 • 157 • 163 • 181 • 193 • 211 • 277 • 281 • 353 • 421 • 487 • 829

35

112505380450296606970338459629988782604252033209350010888227147338120001 = 17 • 19 • 23 • 29 • 31 • 37 • 41 • 43 • 53 • 61 • 67 • 71 • 73 • 79 • 89 • 97 • 101 • 109 • 113 • 127 • 131 • 151 • 157 • 163 • 193 • 199 • 211 • 241 • 251 • 271 • 313 • 331 • 337 • 701 • 1327

 

La tabella seguente mostra il numero di numeri di Carmichael con esattamente k fattori primi minori di alcune potenze di 10 (Andrew Granville e Carl Pomerance, 2001).

n

Numeri di Carmichael minori di n

k = 3

k = 4

k = 5

k = 6

k = 7

k = 8

k = 9

k = 10

10

0

0

 

 

 

 

 

 

 

102

0

0

 

 

 

 

 

 

 

103

1

1

 

 

 

 

 

 

 

104

7

7

 

 

 

 

 

 

 

105

16

12

4

 

 

 

 

 

 

106

43

23

19

1

 

 

 

 

 

107

105

47

55

3

 

 

 

 

 

108

255

84

144

27

 

 

 

 

 

109

646

172

314

146

14

 

 

 

 

1010

1547

335

619

492

99

2

 

 

 

1011

3605

590

1179

1336

459

41

 

 

 

1012

8241

1000

2102

3156

1714

262

7

 

 

1013

19279

1858

3639

7082

5270

1340

89

1

1

1014

44706

3284

6042

14938

14401

5359

655

27

27

1015

105212

6083

9938

29282

36907

19210

3622

170

170

1016

246683

10816

16202

55012

86696

60150

16348

1436

23

 

Andrew Granville e Carl Pomerance avanzarono nel 2001 la congettura, supportata da argomenti euristici e dai dati sperimentali, che il numero di numeri di Carmichael minori di n con esattamente k fattori primi sia minore di Limite superiore supposto per il numero di numeri di Carmichael minori di n con k fattori primi, per una costante c che dipende da k, e dimostrarono che è minore di Limite superiore dimostrato per il numero di numeri di Carmichael minori di n con k fattori primi.

 

Il minimo numero di Carmichael che sia prodotto di altri due numeri di Carmichael è 509033161 = 1729 • 294409.

 

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 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).

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.