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, .
Taula de continguts |
[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,
.
- 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 1018 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 (6k + 1)(12k + 1)(18k + 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
. Am. Math. Month. 19 22–27.
- Beeger, N.G.W.H. (1950) On composite numbers n for which
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.