Nombres de Carmichael

sèrie de nombres naturals

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òricaModifica

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]

GeneralitatsModifica

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.

PropietatsModifica

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

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 ChernickModifica

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ènciesModifica

  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. 

BibliografiaModifica