Carmichael nummer

I tallteori er et Carmichael-tall et sammensatt positivt heltall n som tilfredsstiller kongruens

for alle heltall b som er coprime med n eller, tilsvarende, som bekrefter kongruens

for hver b . De er oppkalt etter Robert Carmichael , som fant de første eksemplene.

Fermats lille teorem sier at alle primtall har den egenskapen, men det motsatte er ikke sant: for eksempel , men 341 er ikke primtall, som er produktet av 11 og 31. Et tall som kalles Fermats pseudoprimtall med hensyn til base b ; Carmichaels tall er Fermats pseudoprimer på alle grunnlag, dvs. absolutte .

Carmichaels tall er av betydelig betydning fordi de består Fermat primalitetstesten i alle fall til tross for at de er sammensatt: deres eksistens forhindrer å bruke denne testen for å bekrefte med sikkerhet primaaliteten til et tall, mens det fortsatt kan brukes til å bevise at et tall det er sammensatt.

Egenskaper

En karakterisering av Carmichael-tall ble gitt i 1899 av Korselt: et sammensatt positivt heltall n er et Carmichael-tall hvis og bare hvis det ikke har noen kvadrater og for enhver primtall p av n , p -1 deler n -1.

En følge av dette teoremet er at alle Carmichael-tall er oddetall : hvis n var partall med en oddetallsfaktor p , ville vi ha p -1 | n -1 ( a | b betyr a deler b ), men p -1 ville være partall i motsetning til n-1 , oddetall, og derfor kunne ikke p-1 dele den.

Korselt, mens han demonstrerte denne egenskapen, kunne ikke finne et eksempel; i 1910 fant Robert Daniel Carmichael det minste tallet med denne eiendommen, 561 , og knyttet dermed navnet hans til disse tallene.

Man kan enkelt verifisere at 561 er et Carmichael-tall med Korselts teorem. Faktisk har 561 = 3 · 11 · 17 ingen kvadrater og 2 | 560, 10 | 560 og 16 | 560. Carmichaels påfølgende tall er [1] :

1105 (5 13 17), 1729 (7 13 19), 2465 (5 17 29), 2821 (7 13 31), 6601 (7 23 41), 8911 (7 19 67)

Carmichael-tall har minst tre positive primfaktorer. Carmichaels primtall med k  = 3, 4, 5, ... primtall er [2] :

k
3 561 = 31117
4 41041 = 7111341
5 825265 = 5 7 17 19 73
6 321197185 = 5 19 23 29 37 137
7 5394826801 = 7 13 17 23 31 67 73
8 232250619601 = 7111313173137733163
9 9746347772161 = 71113131719313741641

Merkelig nok kan det første Carmichael-tallet (561) uttrykkes som summen av to potenser av første grad på et større antall måter enn et hvilket som helst mindre tall (selv om dette er trivielt sant for ethvert positivt heltall), det andre Carmichael-tallet (1105) ) kan skrives som summen av to kvadrater på flere måter enn noe mindre tall, og Carmichaels tredje tall (1729) er Hardy-Ramanujan- tallet: det minste tallet som kan skrives som summen av to terninger på to forskjellige måter.

Distribusjon

Carmichael-tall er sjeldne: for eksempel er det 1 401 644 Carmichael-tall mellom 1 og 10 18 (omtrent ett for hver 700 milliarder tall). [3] Dette gjør primalitetstester basert på Fermats lille teorem litt mer usikre enn andre, som Solovay-Strassen primalitetstesten .

J. Chernick beviste i 1939 at hvis tallene 6 k +1, 12 k +1 og 18 k +1 er primtall, så er produktet deres et Carmichael-tall; det er imidlertid ikke kjent om tallene i denne formen er endelige eller uendelige.

Paul Erdős viste, med heuristiske grunner, at det burde være uendelige Carmichael-tall, og antok at det for hvert finnes en verdi slik at, kalt C ( x ), antall Carmichael-tall mindre enn eller lik x ,

for hver . [4] I 1994 beviste W. R. (Red) Alford , Andrew Granville og Carl Pomerance uendeligheten av Carmichaels tall, og beviste at for x tilstrekkelig store ,. [5] Glyn Harman forbedret deretter dette resultatet ved å bevise at for x tilstrekkelig stor, [6] og deretter bringe eksponenten til 1/3 [7] .

Et overheadestimat av funksjonen C ( x ) ble levert av Erdős selv, som beviste i 1956 at

for noen konstant k .

Fordelingen av Carmichael-tall mindre enn potenser av 10 er: [3] .

1 2 3 4 5 6 7 8 9 10 11 12 1. 3 14 15 16 17 18 19 20 21
0 0 1 7 16 43 105 255 646 1547 3605 8241 19279 44706 105212 246683 585355 1401644 3381806 8220777 20138200

Tabellen nedenfor viser de omtrentlige verdiene for konstanten k for den øvre grensen gitt av Erdős for med økende n :

3 4 5 6 7 8 9 10 11 12 1. 3 14 15 16 17 18 19 20 21
k 2,93319 2.19547 2,07632 1,97946 1,93388 1,90495 1,87989 1,86870 1,86421 1,86377 1,8624 1,86293 1,86301 1,86406 1,86472 1,86522 1,86565 1,86598 1,86619

Löh og Niebuhr fant noen store Carmichael-tall i 1992 , inkludert en med 1 101 518 faktorer og over 16 millioner sifre.

Carmichael tall av høyere orden

Carmichaels tall kan generaliseres ved å bruke verktøyene til abstrakt algebra .

Den gitte definisjonen sier at et sammensatt heltall n er Carmichaels nøyaktig når den n -te potensfunksjonen p n fra ringen Z n til heltallene modulo n selv er den identiske funksjonen. Identitet er den eneste endomorfismen fra en Z n - algebra i Z n , derfor kan vi omskrive definisjonen ved å kreve at p n er en endomorfisme på Z n . Som før tilfredsstiller p n samme egenskap hvis n er primtall.

Den n -te potensfunksjonen p n er definert i hver Z n -algebra A. En teorem sier at n er primtall hvis og bare hvis alle disse p n funksjonene er endomorfismer.

På grensen mellom disse to betingelsene er definisjonen av Carmichael-tall av orden m , for et positivt heltall m , som et sammensatt tall n slik at p n er en endomorfisme på hver Z n -algebra som kan genereres som Z n - modul av m elementer . Carmichael-numre av ordre 1 er vanlige Carmichael-numre.

Egenskaper

Korselts kriterium kan generaliseres til høyere ordens Carmichael-tall, som vist av Howe. [8]

I samme publikasjon foreslås heuristiske grunner, ifølge hvilke det er uendelige Carmichael-tall av orden m , for hver m . Imidlertid er ingen Carmichael-tall av orden 3 eller høyere kjent.

Merknader

  1. ^ Sequenza A002997 , på On - Line Encyclopedia of Integer Sequences , The OEIS Foundation.
  2. ^ Sequenza A006931 , på On - Line Encyclopedia of Integer Sequences , The OEIS Foundation.
  3. ^ a b Richard Pinch, "The Carmichael numbers up to 10 18 " , april 2006 (forlenger et tidligere arbeid Arkivert kopi ( ps ), på chalcedon.demon.co.uk . URL åpnet 22. april 2007 (arkivert fra den opprinnelige url 1. mars 2007) . [1] [2] ).
  4. ^ Richard Crandall og Carl Pomerance , primtall. A computational perspective , andre, Springer, 2005, s. 133-135, ISBN 0-387-25282-7 .  
  5. ^ WR Alford, A. Granville og C. Pomerance. "Det er uendelig mange Carmichael-tall." Annals of Mathematics 139 (1994) 703-722.
  6. ^ Glyn Harman. "På antall Carmichael-tall opp til X." Okse. Lond. Matte. Soc. 37 (2005) 641-650.
  7. ^ Glyn Harman. "Watts middelverditeorem og Carmichael-tall." International Journal of Number Theory 4 (2008), n. 2, 241-248.
  8. ^ Everett W. Howe. "Carmichael-tall av høyere orden." Mathematics of Computation 69 (2000), s. 1711–1719.

Bibliografi

Relaterte elementer

Andre prosjekter

Eksterne lenker