Carmichael-nummer

I tallteori er et Carmichael-tall (oppkalt etter den amerikanske matematikeren Robert Daniel Carmichael ), eller absolutt pseudo-primtall , et sammensatt tall n som tilfredsstiller følgende egenskaper:

for et hvilket som helst heltall en , n er en divisor av en n - et

eller som (i henhold til Gauss lemma ) tilsvarer:

for ethvert heltall er en prim med n , n en deler av en n - 1 - 1.

Det er derfor et Fermat- pseudo-primtall i en hvilken som helst primærbase med det (vi kan også begrense oss til et område fra 2 til n - 1 i denne definisjonen).

I 1994 viser Alford, Granville og Pomerance at det er uendelig mange av dem.

Kontekst

Den Fermats lille teorem sier at primtall har den egenskapen : For alle heltall en , n er en divisor av en n - en . Dets omvendte er falsk, Carmichaels tall er positive tall som tilfredsstiller uten å være prime, de er Fermat-løgnere ; eksistensen av slike absolutte pseudo-primtall er det som hindrer bruk av Fermats primalitetstest for å bevise at et tall er primtall. ${\ mathcal {P}}$ ${\ mathcal {P}}$

Jo større tall og desto sjeldnere Carmichael-tallene blir, de fleste av dem gjør Fermat -primalitetstesten stort sett ubrukelig sammenlignet med andre primalitetstester som Solovay-Strassen -primalitetstesten . For eksempel, 646 th er Carmichael nummer 993 905 641, og det finnes 105,212 Carmichael tall mellom 1 og 10 15 .

En karakterisering av Carmichael-tall er gitt av Korselts teorem:

Teorem ( Korselt 1899 ) - En sammensatt positivt heltall n er et Carmichael nummer hvis og bare hvis ingen prim kvadratiske dividerer n (vi si at n er uten en kvadratisk faktor ) og for hver primdivisor p av n , antallet p - 1 dividerer n - 1. Videre deler slik n alle a n - a (selv for en ikke prime til n ).

Det følger av denne teoremet at alle Carmichael-tall er produkter av minst tre forskjellige primtall.

Korselt nevner denne karakteriseringen (uten å følge den med eksempler) i et kort svar på et spørsmål fra Gaston Tarry , om, vi vil si i dag, eksistensen av pseudo-primtall i base 2, en tidligere karakterisering tilsynelatende - han så ubemerket. I 1910 uttalte og demonstrerte Robert Daniel Carmichael uavhengig et lignende kriterium, hvis formulering bruker sin indikatorfunksjon , og gir 4 av disse tallene inkludert 561 og 1105, de to minste av dem, resultater som han tar opp og utvikler i en artikkel. utgitt i 1912. Det er etter disse artiklene at disse tallene kalles Carmichael-tall .

Vi kan enkelt bekrefte at 561 = 3 · 11 · 17 er et Carmichael-tall ved hjelp av Korselts teorem: primfaktoriseringen inkluderer ikke en multipelfaktor og 3 - 1 = 2, 11 - 1 = 10 og 17 - 1 = 16 er alle tre delere på 560.

De første syv tallene i Carmichael er:

561 = 3 × 11 × 17 1 105 = 5 × 13 × 17 1729 = 7 × 13 × 19 2465 = 5 × 17 × 29 2 821 = 7 × 13 × 31 6,601 = 7 × 23 × 41 8911 = 7 × 19 × 67.

J. Chernick demonstrerte en setning i 1939 som kan brukes til å konstruere en delmengde av Carmichael-tall. Tallet (6 k + 1) (12 k + 1) (18 k + 1) er et Carmichael-tall hvis de tre faktorene alle er primtall. Det er ikke kjent om denne formelen, eller andre som den, genererer en uendelig Carmichael-tall når k beskriver settet med heltall. Ethvert Chernick-nummer er også et Zeisel-nummer med a = 1 og b = 6k .

Antall Carmichael-tall

I 1956 demonstrerte Paul Erdős eksistensen av en konstant K slik at antallet C ( n ) av Carmichael-tallene mindre enn eller lik n økes med . ${\ displaystyle n \ exp \ left ({\ frac {-K \ ln n \ ln \ ln \ ln n} {\ ln \ ln n}} \ right)}$

Følgende tabell gir de omtrentlige minimumsverdiene for denne konstanten, for n ≤ 10 m :

m	4	6	8	10	12	14	16	18	20
K	2.19547	1.97946	1.90495	1,86870	1,86377	1,86293	1,86406	1,86522	1.86598

I samme papir ga Erdős heuristiske argumenter for hypotesen om at for alle ε> 0, C ( n )> n 1 - ε for n stort nok. Hans hypotese førte til antagelsen om eksistensen av en uendelig Carmichael-tall.

Denne antagelsen ble demonstrert i 1994 av William Alford (en) , Andrew Granville og Carl Pomerance , og de demonstrerte til og med mer presist at C ( n )> n 2/7 for n stort nok.

I 2013 demonstrerte Thomas Wright at det er en uendelig mengde Carmichael-tall i en hvilken som helst aritmetisk sekvens (an + b) der pgcd (a, b) = 1.

Eiendommer

Et hvilket som helst antall Carmichaels er merkelig . For ethvert jevnt sammensatt heltall er n faktisk (–1) n - (–1) = 2 ikke delbart med n .

Carmichaels tall har minst tre hovedfaktorer.

De viktigste Carmichael-tallene med henholdsvis minst k = 3, 4, 5, ... primfaktorer er (suite A006931 fra OEIS ):

k
3	561 = 31117
4	41041 = 7111341
5	825265 = 5 7 17 19 73
6	321197185 = 5 19 23 29 37 137
7	5394826801 = 7131723316773
8	232250619601 = 7111317313773163
9	9746347772161 = 711131719313741641

Primimes Carmichael med de første fire faktorene er (forts. A074379 fra OEIS ):

Jeg
1	41041 = 7111341
2	62745 = 3 · 5 · 47 · 89
3	63973 = 7131937
4	75361 = 11131731
5	101101 = 71113101
6	126217 = 7131973
7	172081 = 7133161
8	188461 = 71319109
9	278545 = 51729113
10	340561 = 13172367

En morsom tilfeldighet er dette: det tredje Carmichael-tallet og det første Chernick-tallet, 1729, er Hardy-Ramanujan-tallet , dvs. det minste positive heltallet som kan skrives på to forskjellige måter som summen av to kuber (1729 = 7 × 13 × 19 = 10 3 + 9 3 = 12 3 + 1 3 ). Likeledes kan Carmichaels andre nummer, 1105, skrives som summen av to firkanter på flere måter enn noe heltall mindre enn det.

Bevis på Korselts teorem

La n være et Carmichael-tall (derfor merkelig), p en av dets primære faktorer, r eksponenten til p i n , og et et heltall som både er generator for den sykliske gruppen av enheter på ℤ / p r ℤ og prim med n / p r (det er noen, ifølge den kinesiske setningen ). Da er en n - 1 - delelig med n, derfor med p r , så n - 1 er et multiplum av multiplikasjonsrekkefølgen til en modulo p r , dvs. av p r - 1 ( p - 1). Det følger at r = 1 (siden p r - 1 deler n - 1 og n ) og at p - 1 deler n - 1.
Motsett, anta at n er et produkt av forskjellige primtall p 1 , p 2 , ..., p k og at tallene p 1 - 1, p 2 - 1, ... alle deler n - 1. For hvert heltall a og alt i , vi har n ≡ 1 (mod p i - 1) og derfor (ifølge Fermats lille setning ) en n ≡ a (mod p i ). Tallet et n er kongruent til en modulo hver av de p- i , slik at også modulo sitt produkt n . Dette gjelder for ethvert heltall a (selv ikke prime til n ), spesielt n er et Carmichael-nummer så snart k > 1.

Dette fullfører beviset på Korselts teorem.

Konsekvenser av Korselts teorem:

Hvis p er en primærfaktor av et Carmichael-tall n , har vi modulo p - 1 n / p = ( n / p ) 1 ≡ ( n / p ) p = n ≡ 1. Med andre ord, hvis p er en primfaktor for et Carmichael-tall, så er produktet av de andre primfaktorene kongruent til 1 modulo p - 1.

Et Carmichael-tall kan ikke være et produkt av to primtall p og q , for da vil hvert av de to tallene p - 1 og q - 1 dele det andre og de vil være like.

Ethvert Carmichael-tall er derfor produktet av minst tre forskjellige (odde) primtall.

Higher Order Carmichael Numbers

Carmichael-tall kan generaliseres ved hjelp av begreper fra generell algebra .

Ovennevnte definisjon sier at en hel forbindelse n er et tall fra Carmichael nettopp når funksjonen n makt p n av kommutativringen Z n av heltall modulo n i seg selv er identitetsfunksjonen. Identiteten er den eneste Z n - endomorfisme av algebra over Z n, slik at vi kan gjenopprette definisjonen som ber om at p n er en endomorfism algebra Z n . Som ovenfor tilfredsstiller p n de samme egenskapene når n er prim.

Funksjonen n- te potens p n også er definert på en hvilken som helst Z n -algebra A . En teorem sier at n er primær hvis og bare hvis alle funksjoner slik at p n er endomorfier av algebraer.

Mellom disse to forholdene er definisjonen av Carmichael-rekkefølgen m for ethvert positivt heltall m som ethvert sammensatt tall n slik at p n er en endomorfisme på hver Z n -algebra som kan genereres som en Z n - modul av m elementer . Første ordens Carmichael-tall er ganske enkelt de vanlige Carmichael-tallene.

Eiendommer

Korselt-kriteriet kan generaliseres til høyere ordre Carmichael-tall.

Et heuristisk argument synes å antyde at det er uendelig mange Carmichael-antall ordre m , uavhengig av m . Imidlertid er ikke noe Carmichaels av ordre 3 eller flere kjent.

Merknader og referanser

(fr) Denne artikkelen er delvis eller helt hentet fra den engelske Wikipedia- artikkelen med tittelen " Carmichael number " ( se listen over forfattere ) .

(i) William Alford, Andrew Granville og Carl Pomerance , " Det er uendelig mange Carmichael-tall " , Ann. av matematikk. , vol. 140, n o 3,1994, s. 703-722 ( les online ).
AR Korselt , " Kinesisk problem [svar på et spørsmål av G. Tarry] ", L'Intermediate des mathématiciens , vol. 6,1899, s. 143 ( les online ), les også (fullstendig bind 5 og 6) . Spørsmålet blir stilt av Tarry i samme tidsskrift i 1988, se bind 5 s 266, svarene, blant annet det fra Korselt, går fra side 142 til side 144 i bind 6.
Ribenboim 1996 , s. 118.
(en) RD Carmichael, " rating was new number theory function " , Bull. Bitter. Matte. Soc. , vol. 16, n o 5,1910, s. 232–238 ( DOI 10.1090 / s0002-9904-1910-01892-9 , les online ), s. 237-238 .
Carmichael, RD, “ På sammensatte tall P som tilfredsstiller Fermat-kongruensen en P -1 ≡ 1 mod P ”, Amer. Matte. Månedlig , vol. 19, n o to1912, s. 22–27 ( DOI 10.2307 / 2972687 ).
For de første 10 000, se denne lenken Suite A002997 fra OEIS . Primfaktoriseringen av 8 241 primtall er gitt her .
(i) J. Chernick, " We Fermats teorem easy " , Bull. Bitter. Matte. Soc. , vol. 45,1939, s. 269-274 ( les online ).
(in) P. Erdős, " We pseudoprimes and Carmichael numbers " , Publ. Matte. Debrecen , vol. 4,1956, s. 201-206 ( les online ).
En numerisk eksperiment gir C (10 21 ) = 20 138 200 ( (en) Richard GE klemme, De Carmichael tallene opp til 10 til 21 , på hans personlige side ), betydelig større enn 10 6 .
(in) Thomas Wright, "Uendelig mange Carmichael-tall i aritmetiske progresjoner", Bull. London matematikk. Soc. , flygning. 45, 2013, s. 943-952 " 1212.5850 " , tekst i fri tilgang, på arXiv ..
(i) Everett W. Howe, "High-order Carmichael numbers", Math. Komp. , flygning. 69, 2000, s. 1711-1719 " matematikk.NT / 9812089 " , tekst i fri tilgang, på arXiv ..

Bibliografi

(no) Paulo Ribenboim , The New Book of Prime Number Records , Springer,1996, 541 s. ( ISBN 0-387-94457-5 ) , kap. IX

Se også

Relatert artikkel

Knödel nummer (i)

Eksterne linker

(no) Dullness of 1729 på mathpages.com
(en) Richard Guy , uløste problemer i tallteori , 3 e ed., Springer Verlag , 2004 Seksjon A13
(en) G. Ander Steele, “ Carmichael tall i antall ringer ” , J. Number Theor. , vol. 128, n o 4,2008, s. 910-917 ( DOI 10.1016 / j.jnt.2007.08.009 , les online )