Carmichael nummer

Carmichael-tallet er et sammensat tal , der opfylder kongruens for alle heltal coprime til , med andre ord en pseudoprime i hver base coprime til . Sådanne tal er relativt sjældne, men de er uendelige i antal, det mindste af dem er 561; eksistensen af sådanne tal gør betingelsen om enkelhed i Fermats lille sætning utilstrækkelig , og tillader ikke brugen af Fermats test som et universelt middel til at kontrollere enkelhed. $n$ $b^{{n-1}}\equiv 1{\pmod {n}}$ $b$ $n$ $b$ $n$

Opkaldt efter den amerikanske matematiker Robert Carmichael .

Generel information

Fermats lille sætning siger, at hvis er et primtal og er et heltal, der ikke er deleligt med , så er det deleligt med , det vil sige . Carmichael-tal er sammensatte, og dette forhold gælder for dem. Carmichael-tal kaldes også absolut pseudoprime Fermat-tal, da de er pseudoprime Fermat-tal i hver coprime-base med dem. $n$ $b$ $n$ $b^{{n-1}}-1$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Eksistensen af Carmichael-tal gør Fermat-primalitetstesten mindre effektiv til at detektere primtal, sammenlignet med for eksempel den mere stringente Nightingale-Strassen-test , som anerkender disse tal som sammensatte. Efterhånden som Carmichaels antal stiger, bliver de sjældnere. For eksempel er der i området fra 1 til 1021 20.138.200 af dem (ca. én ud af 50 billioner tal). Det er dog blevet bevist, at der er uendeligt mange Carmichael-tal [1] .

Historie

Den første person, der opdagede de numeriske egenskaber, der senere blev karakteristiske for Carmichaels tal, var Alvin Corselt , som i 1899 beviste en heltalssætning svarende til vendingsbetingelserne for Fermats lille sætning, det vil sige for heltal , som den gælder for alle heltal . : et sammensat tal er et Carmichael-tal, hvis og kun hvis det er kvadratfrit, og for hver prime divisor af tallet deler tallet tallet [2] . $n$ $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $n$ $s$ $n$ $p-1$ $n-1$

Bevis for Corselts sætning [2] .

Lad det for alle heltal . Lad os først bevise, at tallet skal være firkantfrit. Antag at dette ikke er tilfældet og ( deler ) for et eller andet heltal . Lad da . Da dette forhold er sandt modulo , det vil sige , som modsiger udtrykket . Således er tallet fri for firkanter. Lad nu være en prime divisor af . Det er kendt, at den multiplikative gruppe af ringen af rester modulo , hvor er prime, er en cyklisk gruppe af orden . Lade være et heltal, sådan som er generatoren af gruppen . Siden , så har vi , og siden og er coprimtal, så . Da rækkefølgen af et primitivt element i en gruppe er , følger det . $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $k^{2}\midt n$ $k^{2}$ $n$ $k>1$ $b=k$ $k^{n}\equiv k\pmod{n}$ $k^{2}\midt n$ $k^{2}$ $k^{n}\equiv k\pmod{k^2}$ $k^{n}\equiv 0\pmod{k^2}$ $n$ $s$ $n$ $(\mathbb{Z}/p\mathbb{Z})^*$ $s$ $s$ $p-1$ $b$ $b\pmod{p}$ $(\mathbb{Z}/p\mathbb{Z})^*$ $b^{{n}}\equiv b{\pmod {n}}$ $b^{n}\equiv b\pmod{p}$ $b$ $s$ $b^{n-1}\equiv 1\pmod{p}$ $b\pmod{p}$ $(\mathbb{Z}/p\mathbb{Z})^*$ $p-1$ $p-1\midt n-1$

Antag på den anden side, at det er fri for firkanter og for enhver prime . Lade være nogle primtal dividere , og tallet være et heltal. $n$ $p-1\midt n-1$ $p | n$ $s$ $n$ $b$

Det følger af Fermats lille sætning, at hvis er et primtal og er et heltal, så for ethvert positivt heltal , således at . (Lad , hvor er et positivt heltal. Siden , derfor ) $s$ $b$ $b^{k}\equiv b\pmod{p}$ $k$ $p-1\midt 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))$

Så for et bestemt tilfælde har vi, der er deleligt med enhver prime divisor af tallet , da det er fri for kvadrater, så er det deleligt med , Det vil sige . Dermed er Corselts sætning bevist. $k=n$ $b^n-b$ $n$ $n$ $b^n-b$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Corselt lod spørgsmålet om at finde sammensatte tal, der opfylder dette kriterium, stå åbent. I 1910 formulerede Carmichael et kriterium, der i det væsentlige falder sammen med Corselt-kriteriet, og gav et eksempel på et sammensat tal , som det er opfyldt for - . Dette tal er faktoriseret som 561 = 3 11 17, og derfor fri for kvadrater, mens det er deleligt med 2, 10 og 16. Derefter blev alle modeksempler kaldt Carmichael-tal. $n$ $n=561$ $561-1=560$

Især følger det af Corselts teorem, at alle Carmichael-tal er ulige, da ethvert lige kvadrat-frit sammensat tal har mindst én ulige prim-divisor, og derfor indebærer delelighed, at et lige tal deler et ulige tal, hvilket er umuligt. $p-1\midt n-1$

I 1939 beviste John Chernick et teorem, der kan bruges til at konstruere en delmængde af Carmichael-tal: hvis , , er primtal for en naturlig , så er deres produkt et Carmichael-tal [2] . Denne betingelse kan kun være opfyldt, hvis tallet slutter med cifrene 0, 1, 5 eller 6 i grundtallet 10, det vil sige, at det kan sammenlignes med 0 eller 1 modulo 5. For faktorerne er f.eks. , og , hhv . og deres produkt giver 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 måde at finde Carmichaels tal på kan udvides med antallet af 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

forudsat at alle faktorer er primtal og delelige med . $m$ $2^{{k-4}}$

Hypotesen om uendeligheden af sådanne tal blev udtrykt af Carmichael i 1912, Cherniks teorem øgede spekulativt sandsynligheden for dens implementering; senere underbyggede Pal Erdős heuristisk uendeligheden af Carmichaels tal. Det var dog først i 1992 [2] , at denne påstand blev strengt bevist af William Alford, Andrew Granville og Carl Pomerance [1] , mere præcist: det blev bevist, at der er Carmichael-tal mellem 1 og tilstrækkeligt store . $n$ $n^{{2/7}}$

I 1992 foreslog Günter Le og Wolfgang Niebuhr en ny algoritme til at konstruere store Carmichael-tal: det lykkedes dem at finde tallet opnået ved at gange 1.101.518 primtal; dette nummer indeholder 16.142.049 cifre [3] .

Egenskaber

Bigers og Duparcs sætninger

I 1956 viste Biger, at hvis for primtal , og forholdet og er Carmichaels tal, så og . Således er antallet af Carmichael-tal opnået ved produktet af tre primfaktorer, hvoraf den ene selvfølgelig er kendt. $s$ $q$ $r$ $p<q<r$ $pqr$ $q<2p^{2}$ $r<p^{3}$

Duparc generaliserede senere dette resultat for at vise, at hvis er et Carmichael-tal, hvor og er primtal, så og . Derfor er der højst et endeligt antal Carmichael-tal med alle på nær to definerede faktorer. $n=mqr$ $q$ $r$ $q<2m^{2}$ $r<m^{3}$

Case = 1 viser, at ethvert Carmichael-tal indeholder mindst 3 primfaktorer, denne konklusion blev først lavet af Carmichael selv. $m$

Primfaktoriseringer

Primfaktoriseringerne af de første par Carmichael-tal er som følger:

{\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\midt 1104;12\midt 1104;16\midt 1104),\\1729=7\cdot 13\cdot 19&\qquad (6\midt 1728;12\midt 1728;18\midt 1728),\\2465 =5\cdot 17\cdot 29&\qquad (4\midt 2464;16\midt 2464;28\midt 2464),\\2821=7\cdot 13\cdot 31&\qquad (6\midt 2820;12\midt 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\midt 8910;18\midt 8910;66\midt 8910).\end{aligned}}

Carmichael-tal har mindst tre positive primfaktorer. De første Carmichael-tal med primfaktorer [4] : $k=3,4,5,\ldots$

k
3	$561=3\cdot 11\cdot 17$
fire	$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$
otte	$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ørste Carmichael-tal med fire primfaktorer [5] :

jeg
en	$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$
fire	$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$
otte	$188461=7\cdot 13\cdot 19\cdot 109$
9	$278545=5\cdot 17\cdot 29\cdot 113$
ti	$340561=13\cdot 17\cdot 23\cdot 67$

Fordeling

Følgende tabel viser antallet af Carmichael-tal mindre end eller lig med , som er givet som en potens af ti: [6] $C(X)$ $x$ $n$

$n$	en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten	16
$C(10^{n})$	0	0	en	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683

I 1953 beviste Walter Knödel , at:

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

for nogle konstante . $k_{1}$

Lad betegne antallet af Carmichael-tal mindre end . Det beviste Erdős i 1956 $C(X)$ $x$

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

for nogle konstante . Samtidig blev det også bevist [1] at der er uendeligt mange Carmichael-tal, altså . $k_{2}$ $\lim _{{X\to \infty }}C(X)=\infty$

Følgende tabel viser de omtrentlige minimumsværdier af konstanten k for værdier X = 10 n for forskellige n :

$n$	fire	6	otte	ti	12	fjorten	16	atten	tyve	21
k	2.19547	1,97946	1,90495	1,86870	1,86377	1,86293	1,86406	1,86522	1,86598	1,86619

Sjældne egenskaber ved individuelle tal

Det andet Carmichael-tal (1105) kan repræsenteres som summen af to kvadrater på flere måder end et hvilket som helst mindre tal.

Det tredje Carmichael-tal ( 1729 ) er Ramanujan-Hardy- tallet (det mindste tal, der kan repræsenteres som summen af to terninger på to måder).

Noter

↑ 1 2 3 W. R. Alford, A. Granville, C. Pomerance. Der er uendeligt mange Carmichael-numre // Annals of Mathematics : journal . - 1994. - Bd. 139 . - s. 703-722 . - doi : 10.2307/2118576 .
↑ 1 2 3 4 C. Pomerance. Carmichael-numre (neopr.) // Nieuw Arch. Wisk.. - 1993. - S. 199-209 .
↑ G Loh, W. Niebuhr. En ny algoritme til at konstruere store Carmichael-tal // Math . Comp. : journal. - 1996. - Bd. 65 , nr. 214 . - s. 823-836 .
↑ OEIS -sekvens A006931 _
↑ OEIS -sekvens A074379 _
↑ Richard Pinch. "Carmichael-tallene er op til 10^21" (2007). (ubestemt)

Ordbøger og encyklopædier	Britannica (online)