Nombres de Carmichael

Els nombres de Carmichael són els nombres enters no primers que compleixen la congruència de Fermat. Un nombre $n$ és de Carmichael si, per tot enter $a$ coprimer amb $n$ , $a^{n-1}\equiv 1{\pmod {n}}$ .^[1]

Nota històrica

Cap a 1899, Alwin Korselt ja conjecturava l'existència de nombres enters no primers que satisfan la congruència de Fermat, però no en va poder trobar cap. El 1910 Robert Daniel Carmichael en descobrí el primer, el 561, i encara en va trobar després quinze més, cosa que el va fer conjecturar-ne l'existència d'infinits. Aquesta conjectura no es va demostrar certa fins al 1992, a l'article d'Alford, Granville i Pomerance (1994), There are infinitely many Carmichael numbers. El terme nombre de Carmichael l'introduí Beeger el 1950.^[2]

Generalitats

Els nombres de Carmichael són, en certa forma, semblants als nombres primers: són nombres pseudoprimers respecte qualsevol base i, per això, se'ls anomena pseudoprimers absoluts.

Els nombres de Carmichael tenen importància perquè poden falsejar els resultats de la prova de primalitat de Fermat. L'existència d'aquests nombres, però, no inutilitza aquesta prova en el cas que el resultat sigui que el nombre comprovat no és primer.

Propietats

L'anomenat criteri de Korselt estableix que un nombre $n$ és de Carmichael si, i només si, no conté quadrats i qualsevol factor primer $p$ de $n$ compleix que $p-1$ divideix exactament $n-1$ .
Com a conseqüència de l'anterior, els nombres de Carmichael són tots senars.
Els nombres de Carmichael compleixen també la versió general de la congruència de Fermat: un nombre $n$ és de Carmichael si, i només si, per tot enter $a$ , sigui o no coprimer amb $n$ , $a^{n}\equiv a{\pmod {n}}$ .
Un nombre de Carmichael conté, almenys, tres factors primers diferents.
Hi ha infinits nombres de Carmichael, però són rars.^[3] Per exemple, entre 1 i 10¹⁸ n'hi ha només 1.401.644 en una proporció aproximada d'1 a 700.000.000.000. Això fa relativament poc perillosa la prova de primalitat basada en el Petit Teorema de Fermat.
Denotem $C(X)$ com el nombre de nombres de Carmichael majors o iguals que $X$ ; es coneix que aquest nombre està fitat superiorment^[4]^[5] i inferiorment,^[6] però es desconeix la taxa de creixement asimptòtica de $C(X)$ .^[7]

Construcció i exemples

Els primers nombres de Carmichael són

561 = 3 · 11 · 17

1105 = 5 · 13 · 17

1729 = 7 · 13 · 19

2465 = 5 · 17 · 29

2821 = 7 · 13 · 31

6601 = 7 · 23 · 41

8911 = 7 · 19 · 67

tots ells amb tres factors primers. Amb quatre factors primers hi ha

41041 = 7 · 11 · 13 · 41

62745 = 3 · 5 · 47 · 89

63973 = 7 · 13 · 19 · 37

75361 = 11 · 13 · 17 · 31

101101 = 7 · 11 · 13 · 101

126217 = 7 · 13 · 19 · 73

172081 = 7 · 13 · 31 · 61

188461 = 7 · 13 · 19 · 109

278545 = 5 · 17 · 29 · 113

340561 = 13 · 17 · 23 · 67

No es coneix cap expressió general que proporcioni tots els pseudoprimers absoluts. Ara bé, a partir de la fórmula que J. Chernick va proposar l'any 1939, s'han trobat moltes altres expressions semblants per produir-ne d'altres.

Fórmula de Chernick

Al 1939, J. Chernick va trobar una nova manera d'obtenir nombres de Carmichael.^[8]^[9] Si, per un nombre natural n, els tres nombres $6n+1$ , $12n+1$ i $18n+1$ són primers, llavors el producte $M_{3}(n)=(6n+1)(12n+1)(18n+1)$ és un nombre de Carmichael. Aquesta condició només es satisfà si n acaba amb 0, 1, 5 o 6.

Aquesta manera de construir nombres de Carmichael es pot ampliar de la següent manera:^[10]

M_{k}(n)=(6n+1)(12n+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}n+1)

amb la condició que cadascun dels factors és primer i n és divisible per $2^{k-4}$ .

Referències

↑ Carmichael, R. D. (1912). On composite numbers $P$ which satisfy the Fermat congruence $a^{P-1}\equiv 1{\pmod {P}}$ . Am. Math. Month. 19 22–27.
↑ Beeger, N.G.W.H. (1950) On composite numbers $n$ for which $a^{n-1}\equiv 1{\pmod {n}}$ for every $a$ prime to $n$ Scripta Mathematica, 16, pp.133-135
↑ W. R. Alford, A. Granville, and C. Pomerance «There are Infinitely Many Carmichael Numbers». Annals of Mathematics, 139, 1994, pàg. 703-722.
↑ Paul Erdős «On pseudoprimes and Carmichael numbers». Publ. Math. Debrecen, 18, 1956, pàg. 201-206.
↑ C. Pomerance, J.L. Selfridge and S.S. Wagstaff j «The pseudoprimes to $25\cdot 10^{9}$ ». Math. Comp. 35, 1980, pàg. 1003-1026.
↑ Harman, Glyn «On the number of Carmichael numbers up to x». Bulletin of the London Mathematical Society, 37, 2005, pàg. 641–650. DOI: 10.1112/S0024609305004686.
↑ Guy, Richard. Springer-Verlag. Unsolved problems in Number Theory. 3a edició, 2004. ISBN 0-387-20860-7.
↑ Chernick, J. «On Fermat's simple theorem». Bull. Amer. Math. Soc., 45, 1939, pàg. 269-274.
↑ Dubner, H. «A New Method for Producing Large Carmichael Numbers». Mathematics of Computation, 53, 187, 1989, pàg. 411-414.
↑ Ribenboim, Paulo. The new book of primer number records, 1996, p. 120. ISBN 0-387-94457-5.

Bibliografia

Taula de nombres de Carmichael a Viquillibres (alemany)
Korselt A. (1899). Problème Chinois L'Intermédiaire des Mathématiciens, 6, pp.142-143.
Peterson I., Primality tests: An infinity of exceptions, Science News 142
Alford, Granville and Pomerance (1994). There are infinitely many Carmichael numbers, Ann. of Math. 140(3), 703-722.
«Nombres de Carmichael genèrics». Numericana. Arxivat de l'original el 27 de desembre 2009.
Richard E. Crandall; Carl Pomerance Prime Numbers: A Computational Perspective. Springer-Verlag, 2001. ISBN 0-387-25282-7.

[1] Carmichael, R. D. (1912). On composite numbers $P$ which satisfy the Fermat congruence $a^{P-1}\equiv 1{\pmod {P}}$ . Am. Math. Month. 19 22–27.

[2] Beeger, N.G.W.H. (1950) On composite numbers $n$ for which $a^{n-1}\equiv 1{\pmod {n}}$ for every $a$ prime to $n$ Scripta Mathematica, 16, pp.133-135

[3] W. R. Alford, A. Granville, and C. Pomerance «There are Infinitely Many Carmichael Numbers». Annals of Mathematics, 139, 1994, pàg. 703-722.

[4] Paul Erdős «On pseudoprimes and Carmichael numbers». Publ. Math. Debrecen, 18, 1956, pàg. 201-206.

[5] C. Pomerance, J.L. Selfridge and S.S. Wagstaff j «The pseudoprimes to $25\cdot 10^{9}$ ». Math. Comp. 35, 1980, pàg. 1003-1026.

[6] Harman, Glyn «On the number of Carmichael numbers up to x». Bulletin of the London Mathematical Society, 37, 2005, pàg. 641–650. DOI: 10.1112/S0024609305004686.

[7] Guy, Richard. Springer-Verlag. Unsolved problems in Number Theory. 3a edició, 2004. ISBN 0-387-20860-7.

[8] Chernick, J. «On Fermat's simple theorem». Bull. Amer. Math. Soc., 45, 1939, pàg. 269-274.

[9] Dubner, H. «A New Method for Producing Large Carmichael Numbers». Mathematics of Computation, 53, 187, 1989, pàg. 411-414.

[10] Ribenboim, Paulo. The new book of primer number records, 1996, p. 120. ISBN 0-387-94457-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]