Nombres de Carmichael

De Viquipèdia
Salta a la navegació Salta a la cerca

Els nombres de Carmichael són els nombres enters no primers que compleixen la congruència de Fermat. Un nombre és de Carmichael si, per tot enter coprimer amb , .[1]

Nota històrica[modifica]

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[modifica]

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[modifica]

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

Construcció i exemples[modifica]

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[modifica]

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 , i són primers, llavors el producte é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]

amb la condició que cadascun dels factors és primer i n és divisible per .

Referències[modifica]

  1. Carmichael, R. D. (1912). On composite numbers which satisfy the Fermat congruence . Am. Math. Month. 19 22–27.
  2. Beeger, N.G.W.H. (1950) On composite numbers for which for every prime to 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 ». 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. 

Bibliografia[modifica]