Nombres de Carmichael

De Viquipèdia

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}$ .

Taula de continguts

1 Nota històrica
2 Generalitats
3 Propietats
4 Construcció i exemples
5 Referències

[edita] 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 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 el 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.

[edita] Generalitats

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

Els nombres de Carmichael tenen importància perquè poden falsejar els resultats de la prova de primalitat basada en el Petit Teorema 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.

[edita] 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. Per exemple, entre 1 i 10¹⁸ n'hi ha només 1.401.644 en una proporció aproximada de 1 a 700.000.000.000. Això fa relativament poc perillosa la prova de primalitat basada en el Petit Teorema de Fermat.

[edita] Construcció i exemples

Els primers nombres de Carmichael són

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

Com no podia ser menys per aquests nombres pseudoprimers absoluts, no es coneix cap expressió general que els proporcioni tots. Però, a partir de l'observació feta el 1939 per J. Chernik que, si els tres factors són primers, el producte $(6 k + 1)(12 k + 1)(18 k + 1)$ és un nombre de Carmichael, hom ha trobat moltes d'altres expressions semblants per produir-ne d'altres.

[edita] Referències

Taula de nombres de Carmichael
Korselt A. (1899). Problème Chinois L'Intermédiaire des Mathématiciens, 6, pp.142-143.
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
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.