Carmichael nummer

Carmichael-talet är ett sammansatt tal som uppfyller kongruens för alla heltal coprime till , med andra ord en pseudoprime i varje bas coprime till . Sådana tal är relativt sällsynta, men de är oändliga till antalet, det minsta av dem är 561; förekomsten av sådana siffror gör villkoret för enkelhet i Fermats lilla sats otillräckligt , och tillåter inte användningen av Fermats test som ett universellt sätt att kontrollera enkelheten. $n$ $b^{{n-1}}\ekvivalent 1{\pmod {n}}$ $b$ $n$ $b$ $n$

Uppkallad efter den amerikanske matematikern Robert Carmichael .

Allmän information

Fermats lilla sats säger att om är ett primtal och är ett heltal som inte är delbart med , då är det delbart med , det vill säga . Carmichael-tal är sammansatta, och detta förhållande gäller för dem. Carmichael-tal kallas också absolut pseudoprime Fermat-tal, eftersom de är pseudoprime Fermat-tal i varje coprime-bas med dem. $n$ $b$ $n$ $b^{{n-1}}-1$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Förekomsten av Carmichael-tal gör Fermat-primalitetstestet mindre effektivt för att detektera primtal, jämfört med till exempel det mer rigorösa Nightingale-Strassen-testet , som känner igen dessa tal som sammansatta. När Carmichaels antal ökar blir de sällsynta. Till exempel, i intervallet från 1 till 1021 finns det 20 138 200 av dem (ungefär en på 50 biljoner tal). Det har dock bevisats att det finns oändligt många Carmichael-nummer [1] .

Historik

Den första personen som upptäckte de numeriska egenskaperna som senare blev ett kännetecken för Carmichaels tal var Alvin Corselt , som 1899 bevisade ett heltalssats motsvarande omkastningsvillkoren för Fermats lilla sats, det vill säga för heltal , för vilket det gäller för alla heltal : ett sammansatt tal är ett Carmichael-tal om och endast om det är kvadratfritt och för varje primtal divisor av talet delar talet talet [2] . $n$ $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $n$ $sid$ $n$ $p-1$ $n-1$

Bevis för Corselts sats [2] .

Låt det för alla heltal . Låt oss först bevisa att talet måste vara kvadratfritt. Antag att så inte är fallet och ( delar ) för något heltal . Låt då . Eftersom detta förhållande är sant modulo , det vill säga som motsäger uttrycket . Således är numret fritt från rutor. Låt nu vara en primtal divisor av . Det är känt att den multiplikativa gruppen i ringen av rester modulo , där är prime, är en cyklisk grupp av ordning . Låta vara ett heltal som är generatorn av gruppen . Sedan , då har vi , och sedan och är coprimtal, då . Eftersom ordningen för ett primitivt element i en grupp är , följer det att . $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $k^{2}\mid n$ $k^{2}$ $n$ $k>1$ $b=k$ $k^{n}\equiv k\pmod{n}$ $k^{2}\mid n$ $k^{2}$ $k^{n}\equiv k\pmod{k^2}$ $k^{n}\equiv 0\pmod{k^2}$ $n$ $sid$ $n$ $(\mathbb{Z}/p\mathbb{Z})^*$ $sid$ $sid$ $p-1$ $b$ $b\pmod{p}$ $(\mathbb{Z}/p\mathbb{Z})^*$ $b^{{n}}\equiv b{\pmod {n}}$ $b^{n}\equiv b\pmod{p}$ $b$ $sid$ $b^{n-1}\equiv 1\pmod{p}$ $b\pmod{p}$ $(\mathbb{Z}/p\mathbb{Z})^*$ $p-1$ $p-1\mid n-1$

Å andra sidan, anta att det är fritt från rutor och för alla primtal . Låta vara ett primtal som delar , och talet är ett heltal. $n$ $p-1\mid n-1$ $p | n$ $sid$ $n$ $b$

Det följer av Fermats lilla sats att om är ett primtal och är ett heltal, då för varje positivt heltal så att . (Låt , där är ett positivt heltal. Eftersom , därför ) $sid$ $b$ $b^{k}\equiv b\pmod{p}$ $k$ $p-1\mid k-1$ $q\cdot (p-1) = (k-1)$ $q$ $b^{p} \equiv b\cdot b^{p-1} \equiv b \pmod p, b^{p-1} \equiv 1 \pmod p$ $b\cdot b^{p-1}\cdot b^{p-1}\cdot \ldots \cdot b^{p-1}\equiv b\cdot b^{q\cdot (p-1 )}\equiv b\cdot b^{k-1}\equiv b^{k}\equiv b{\pmod {p}}$

Sedan för ett visst fall har vi som är delbart med alla primtalsdelare av numret , eftersom det är fritt från kvadrater, då är det delbart med , det vill säga . Därmed är Corselts sats bevisad. $k=n$ $b^n-b$ $n$ $n$ $b^n-b$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Corselt lämnade öppen frågan om att hitta sammansatta tal som uppfyller detta kriterium. År 1910 formulerade Carmichael ett kriterium som i huvudsak sammanfaller med Corselt-kriteriet, och gav ett exempel på ett sammansatt nummer för vilket det är uppfyllt - . Detta tal är faktoriserat som 561 = 3 11 17, och därför fritt från kvadrater, samtidigt som det är delbart med 2, 10 och 16. Efter det kallades alla motexempel Carmichael-tal. $n$ $n=561$ $561-1=560$

I synnerhet följer det av Corselts teorem att alla Carmichael-tal är udda, eftersom varje jämnt kvadratfritt sammansatt tal har minst en udda primtalsdelare, och därför innebär delbarhet att ett jämnt tal delar ett udda tal, vilket är omöjligt. $p-1\mid n-1$

År 1939 bevisade John Chernick ett teorem som kan användas för att konstruera en delmängd av Carmichael-tal: om , , är primtal för en naturlig , då är deras produkt ett Carmichael-tal [2] . Detta villkor kan endast uppfyllas om talet slutar med siffrorna 0, 1, 5 eller 6 i bas 10, det vill säga det är jämförbart med 0 eller 1 modulo 5. Till exempel för faktorerna är , och , respektive , och deras produkt ger Carmichaels nummer 1729 . $6m+1$ $12m+1$ $18m+1$ $m$ $M_{3}(m)=(6m+1)(12m+1)(18m+1)$ $m$ $m$ $m=1$ $7$ $13$ $19$

Cherniks sätt att hitta Carmichaels siffror kan utökas med antalet faktorer : $k\geqslant 3$

M_{k}(m)=(6m+1)(12m+1)\prod _{i=1}^{k-2}(9\cdot 2^{i}m+1),\ quad k\geqslant 3

förutsatt att alla faktorer är primtal och delbara med . $m$ $2^{{k-4}}$

Hypotesen om oändligheten av sådana siffror uttrycktes av Carmichael 1912, Cherniks teorem ökade spekulativt sannolikheten för dess genomförande; senare underbyggde Pal Erdős heuristiskt oändligheten av Carmichaels siffror. Det var dock inte förrän 1992 [2] som detta påstående rigoröst bevisades av William Alford, Andrew Granville och Carl Pomerance [1] , mer exakt: det bevisades att det finns Carmichael-tal mellan 1 och tillräckligt stora . $n$ $n^{{2/7}}$

1992 föreslog Günter Le och Wolfgang Niebuhr en ny algoritm för att konstruera stora Carmichael-tal: de lyckades hitta talet som erhölls genom att multiplicera 1 101 518 primtal; detta nummer innehåller 16 142 049 siffror [3] .

Egenskaper

Bigers och Duparcs satser

1956 visade Biger att om för primtal , och relationen och är Carmichaels tal, då och . Således är antalet Carmichael-tal som erhålls av produkten av tre primtalsfaktorer, varav en är känd, naturligtvis. $sid$ $q$ $r$ $p<q<r$ $pqr$ $q<2p^{2}$ $r<p^{3}$

Duparc generaliserade senare detta resultat för att visa att om är ett Carmichael-tal, där och är primtal, då och . Därför finns det som mest ett ändligt antal Carmichael-tal med alla utom två definierade faktorer. $n=mqr$ $q$ $r$ $q<2m^{2}$ $r<m^{3}$

Fall = 1 visar att vilket Carmichael-tal som helst innehåller minst 3 primtalsfaktorer, denna slutsats gjordes först av Carmichael själv. $m$

Primfaktoriseringar

Primfaktoriseringarna av de första Carmichael-talen är som följer:

{\begin{aligned}561=3\cdot 11\cdot 17&\qquad (2\mid 560;10\mid 560;16\mid 560),\\1105=5\cdot 13\cdot 17&\qquad (4\mitten av 1104;12\mitten av 1104;16\mitten av 1104),\\1729=7\cdot 13\cdot 19&\qquad (6\mitten 1728;12\mitten av 1728;18\mitten av 1728),\\2465 =5\cdot 17\cdot 29&\qquad (4\mitten 2464;16\mitten 2464;28\mitten 2464),\\2821=7\cdot 13\cdot 31&\qquad (6\mitten 2820;12\mitten av 2820 ;30\mid 2820),\\6601=7\cdot 23\cdot 41&\qquad (6\mid 6600;22\mid 6600;40\mid 6600),\\8911=7\cdot 19\cdot 67&\qquad (6\mid 8910;18\mid 8910;66\mid 8910).\end{aligned}}

Carmichael-tal har minst tre positiva primtalsfaktorer. De första Carmichael-talen med primtal [4] : $k=3,4,5,\ldots$

k
3	$561=3\cdot 11\cdot 17$
fyra	$41041=7\cdot 11\cdot 13\cdot 41$
5	$825265=5\cdot 7\cdot 17\cdot 19\cdot 73$
6	$321197185=5\cdot 19\cdot 23\cdot 29\cdot 37\cdot 137$
7	$5394826801=7\cdot 13\cdot 17\cdot 23\cdot 31\cdot 67\cdot 73$
åtta	$232250619601=7\cdot 11\cdot 13\cdot 17\cdot 31\cdot 37\cdot 73\cdot 163$
9	$9746347772161=7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 31\cdot 37\cdot 41\cdot 641$

Första Carmichael-talen med fyra primtalsfaktorer [5] :

i
ett	$41041=7\cdot 11\cdot 13\cdot 41$
2	$62745=3\cdot 5\cdot 47\cdot 89$
3	$63973=7\cdot 13\cdot 19\cdot 37$
fyra	$75361=11\cdot 13\cdot 17\cdot 31$
5	$101101=7\cdot 11\cdot 13\cdot 101$
6	$126217=7\cdot 13\cdot 19\cdot 73$
7	$172081=7\cdot 13\cdot 31\cdot 61$
åtta	$188461=7\cdot 13\cdot 19\cdot 109$
9	$278545=5\cdot 17\cdot 29\cdot 113$
tio	$340561=13\cdot 17\cdot 23\cdot 67$

Distribution

Följande tabell visar antalet Carmichael-tal mindre än eller lika med , som ges som en potens av tio: [6] $C(X)$ $X$ $n$

$n$	ett	2	3	fyra	5	6	7	åtta	9	tio	elva	12	13	fjorton	femton	16
$C(10^{n})$	0	0	ett	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683

1953 bevisade Walter Knödel att:

C(X)<X\exp \left({-k_{1}\left(\log X\log \log X\right)^{{\frac {1}{2))))\right)

för någon konstant . $k_{1}$

Låt beteckna antalet Carmichael-tal mindre än . Erdős bevisade det 1956 $C(X)$ $X$

C(X)<X\exp {{\frac {-k_{2}\log {X}\log {\log {\log {X)))){\log {\log {X))))}

för någon konstant . Samtidigt bevisades det också [1] att det finns oändligt många Carmichael-tal, det vill säga . $k_{2}$ $\lim _{{X\to \infty }}C(X)=\infty$

Följande tabell visar de ungefärliga minimivärdena för konstanten k för värden X = 10 n för olika n :

$n$	fyra	6	åtta	tio	12	fjorton	16	arton	tjugo	21
k	2,19547	1,97946	1,90495	1,86870	1,86377	1,86293	1,86406	1,86522	1,86598	1,86619

Sällsynta egenskaper hos enskilda nummer

Det andra Carmichael-talet (1105) kan representeras som summan av två kvadrater på fler sätt än något mindre tal.

Det tredje Carmichael-talet ( 1729 ) är Ramanujan-Hardy- talet (det minsta talet som kan representeras som summan av två kuber på två sätt).

Anteckningar

↑ 1 2 3 W. R. Alford, A. Granville, C. Pomerance. Det finns oändligt många Carmichael Numbers // Annals of Mathematics : journal . - 1994. - Vol. 139 . - s. 703-722 . - doi : 10.2307/2118576 .
↑ 1 2 3 4 C. Pomerans. Carmichael-nummer (neopr.) // Nieuw Arch. Wisk.. - 1993. - S. 199-209 .
↑ G Loh, W. Niebuhr. En ny algoritm för att konstruera stora Carmichael-tal // Math . Comp. : journal. - 1996. - Vol. 65 , nr. 214 . - s. 823-836 .
↑ OEIS - sekvens A006931 _
↑ OEIS - sekvens A074379 _
↑ Richard Pinch. "Carmichael siffror upp till 10^21" (2007). (obestämd)

Ordböcker och uppslagsverk	Britannica (online)