Nombres de Carmichael

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

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]

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.

• L'anomenat criteri de Korselt estableix que un nombre ${\displaystyle n}$ és de Carmichael si, i només si, no conté quadrats i qualsevol factor primer ${\displaystyle p}$ de ${\displaystyle n}$ compleix que ${\displaystyle p-1}$ divideix exactament ${\displaystyle 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 ${\displaystyle n}$ és de Carmichael si, i només si, per tot enter ${\displaystyle a}$, sigui o no coprimer amb ${\displaystyle n}$, ${\displaystyle 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 ${\displaystyle C(X)}$ com el nombre de nombres de Carmichael majors o iguals que ${\displaystyle X}$; es coneix que aquest nombre està fitat superiorment^[4][5] i inferiorment,^[6] però es desconeix la taxa de creixement asimptòtica de ${\displaystyle C(X)}$.^[7]

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.

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 ${\displaystyle 6n+1}$, ${\displaystyle 12n+1}$ i ${\displaystyle 18n+1}$ són primers, llavors el producte ${\displaystyle 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]

${\displaystyle 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 ${\displaystyle 2^{k-4}}$.

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