Carmichael nummer

I talteorin är ett Carmichael-tal ett sammansatt tal $n$ , som i modulär aritmetik uppfyller kongruensrelationen :

$b^{n}\equiv b{\pmod {n}}$

för alla heltal $b$ . Relationen kan också uttryckas i formen:

$b^{n-1}\equiv 1{\pmod {n}}$ .

för alla heltal $b$ som är relativt primtal till $n$ . Carmichael siffror är uppkallade efter den amerikanske matematikern Robert Carmichael , termen har introducerats av Nicolaas Beeger 1950 ( Øystein Ore hade hänvisat till dem 1948 som siffror med "Fermat-egenskapen", eller " F -nummer" för kort). De är oändliga till antalet.

Robert Daniel Carmichael

De utgör de jämförelsevis sällsynta fall där den strikta motsatsen till Fermats lilla sats inte håller. Detta faktum utesluter användningen av det teorem som ett absolut test av primatitet .

Carmichael-talen bildar delmängden K ₁ av Knödel-talen .

Översikt

Fermats lilla sats säger att om $p$ är ett primtal , så är talet b $displaystyle$$^{p}-b}$ en heltalsmultipel för vilket heltal som helst b { $p$ . Carmichael-tal är sammansatta tal som har samma egenskap. Carmichael-tal kallas också Fermat-pseudoprimer eller absoluta Fermat-pseudoprimer . Ett Carmichael-tal kommer att klara ett Fermat-primtalitetstest till varje bas $b$ relativt primtal till talet, även om det faktiskt inte är primtal. Detta gör tester baserade på Fermats Little Theorem mindre effektiva än starka sannolika primitetstester som Baillie-PSW-primalitetstestet och Miller-Rabin-primalitetstestet .

Men inget Carmichael-tal är antingen ett Euler–Jacobi-pseudoprimtal eller ett starkt pseudoprimtal för varje bas relativt primtal till det, så i teorin kan antingen ett Euler- eller ett starkt troligt primtal bevisa att ett Carmichael-tal i själva verket är sammansatt.

Arnault ger ett 397-siffrigt Carmichael-tal $N$ som är ett starkt pseudoprimtal till alla primtalsbaser mindre än 307:

$N=p\cdot (313(p-1)+1)\cdot (353(p- 1)+1)$

var

$p=$ 2967449566868551055015417464290533273077199179985304335099507553127683875317177019859614262818594162359418959416230 8345562493168782883

är ett 131-siffrigt primtal. $p$ är den minsta primtalsfaktorn av $N$ , så detta Carmichael-tal är också ett (inte nödvändigtvis starkt) pseudoprimtal till alla baser mindre än $p$ .

När antalet blir större blir Carmichael-siffror allt mer sällsynta. Till exempel finns det 20 138 200 Carmichael-nummer mellan 1 och 10 ²¹ (ungefär en på 50 biljoner (5·10 ¹³ ) nummer).

Korselts kriterium

En alternativ och likvärdig definition av Carmichael-tal ges av Korselts kriterium .

Sats ( A. Korselt 1899): Ett positivt sammansatt heltal $n$ är ett Carmichael-tal om och endast om $n$ är kvadratfritt , och för alla primtalsdelare $p$ av $n$ , det är sant att $p-1\mid n-1$ .

Det följer av denna sats att alla Carmichael-tal är udda , eftersom alla jämna sammansatta tal som är kvadratfritt (och därför bara har en primtalsfaktor av två) kommer att ha minst en udda primtalsfaktor, och därmed $p-1\mid n-1$ resulterar i en jämn division av en udda, en motsägelse. (Det udda hos Carmichael-tal följer också av det faktum att $-1$ är ett Fermat-vittne för alla jämna sammansatta tal.) Av kriteriet följer också att Carmichael-tal är cykliska . Dessutom följer att det inte finns några Carmichael-tal med exakt två primtalsdelare.

Upptäckt

Korselt var den första som observerade de grundläggande egenskaperna hos Carmichael-tal, men han gav inga exempel. År 1910 hittade Carmichael det första och minsta numret, 561, vilket förklarar namnet "Carmichael-numret".

Václav Šimerka listade de första sju Carmichael-numren

Att 561 är ett Carmichael-nummer kan ses med Korselts kriterium. Faktum är att $561=3\cdot 11\cdot 17$ är kvadratfritt och $2\mid 560$ , ${\middisplaystyle 560}$ och $16\mid 560$ .

De nästa sex Carmichael-numren är (sekvens A002997 i OEIS ):

$1105=5\cdot 13\cdot 17\qquad 1;\mid 01;\d 6 \mid 1104)$

$1729=7\cdot 13\cdot 169\cdot 1728 1728;\quad 18\mitten av 1728)$

$2465=2465=15\cd 2465=15 4; \quad 16\mid 2464;\quad 28\mid 2464)$

${\1display ( 6 \ MID 2820; \ Quad 12 \ Mid 2820; \ Quad 30 \ Mid 2820)}$

$quad 22\mid 6600;\quad 40\mid 6600)} 8911$

${\ DisplayStyle 6601 = 7 \ CDOT 23 \ \ \ cdot 41\qquad (6\mid 6600;$

$8911=7\cdot 19\cdot 67\qquad (6\mid 8910;\quad 18\mid 8910;\quad 66\mid 8910).$

Dessa första sju Carmichael-nummer, från 561 till 8911, hittades alla av den tjeckiske matematikern Václav Šimerka 1885 (föregående alltså inte bara Carmichael utan även Korselt, även om Šimerka inte hittade något liknande Korselts kriterium). Hans arbete förblev dock obemärkt.

Jack Chernick bevisade ett teorem 1939 som kan användas för att konstruera en delmängd av Carmichael-tal. Talet $(6k+1)(12k+1)(18k+1)$ är ett Carmichael-tal om alla dess tre faktorer är primtal . Huruvida denna formel producerar en oändlig mängd Carmichael-tal är en öppen fråga (även om det antyds av Dicksons gissningar ).

Paul Erdős hävdade heuristiskt att det borde finnas oändligt många Carmichael-nummer. 1994 WR (Red) Alford, Andrew Granville och Carl Pomerance en gräns på Olsons konstant för att visa att det verkligen existerar oändligt många Carmichael-nummer. ${\displaystyle n^{2/7}} Carmichael$ visade de att för tillräckligt stora $n$ finns det minst tal mellan 1 och $n.$

Thomas Wright bevisade att om $a$ och $m$ är relativt primtal, så finns det oändligt många Carmichael-tal i den aritmetiska progressionen $a+k\cdot m$ , där $k=1,2,\ldots$ .

Löh och Niebuhr hittade 1992 några mycket stora Carmichael-tal, inklusive ett med 1 101 518 faktorer och över 16 miljoner siffror. Detta har förbättrats till 10 333 229 505 primtalsfaktorer och 295 486 761 787 siffror, så det största kända Carmichael-talet är mycket större än det största kända primtal .

Egenskaper

Faktoriseringar

Carmichael-tal har minst tre positiva primtalsfaktorer. De första Carmichael-talen med $k=3,4,5,\ldots$ primtalsfaktorer är (sekvens A006931 i OEIS ):

k
3	$561=3\cdot 11\cdot 17\,$
4	$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 317\cdot,$
7	${\displaystyle 5394826801=7\cdot 13\cdot 17\cdot 23\cdot 7\cdot 23\cdot}\cdot 23\cdot$
8	$232250619601=7\cdot 11\cdot 11\cdot 7\cdot 11\cdot 1 punkt 73\cdot 163\,$
9	$9746347772161=11\cdot 11\cdot 11\cdot 11\cdot \cdot 31\cdot 37\cdot 41\cdot 641\ ,$

De första Carmichael-talen med 4 primtalsfaktorer är (sekvens A074379 i OEIS ):

i
1	$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\,$
4	$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\,$
8	$188461=7\cdot 13\cdot 19\cdot 109\,$
9	$278545=5\cdot 17\cdot 29\cdot 113\,$
10	$340561=13\cdot 17\cdot 23\cdot 67\,$

Det andra Carmichael-talet (1105) kan uttryckas som summan av två kvadrater på fler sätt än något mindre tal. Det tredje Carmichael-talet (1729) är Hardy-Ramanujan-talet : det minsta talet som kan uttryckas som summan av två kuber (av positiva tal) på två olika sätt.

Distribution

Låt $C(X)$ beteckna antalet Carmichael-tal mindre än eller lika med $X$ . Fördelningen av Carmichael-tal med 10 potenser (sekvens A055553 i OEIS ):

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
$C(10^{n})$	0	0	1	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683	585355	1401644	3381806	8220777	20138200

1953 bevisade Knödel den övre gränsen :

$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}$ .

1956 förbättrade Erdős gränsen till

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

för någon konstant $k_{2}$ . Han gav vidare ett heuristiskt argument som antydde att denna övre gräns skulle vara nära den sanna tillväxthastigheten för $C(X)$ .

I den andra riktningen bevisade Alford , Granville och Pomerance 1994 att för tillräckligt stor X ,

$C(X)>X^{\frac {2}{7}}.$

2005 förbättrades denna gräns ytterligare av Harman till

$C(X)>X^{0,332}$

som sedan förbättrade exponenten till ${\displaystyle 0,7039\cdot 0,4736=0,33336704>$ .

När det gäller den asymptotiska fördelningen av Carmichael-tal har det förekommit flera gissningar. 1956 antog Erdős att det fanns $X^{1-o(1)}$ Carmichael-tal för X tillräckligt stora. 1981 vässade Pomerance Erdős heuristiska argument för att anta att det finns åtminstone

$X\cdot L(X)^{-1+o(1)}$

Carmichael siffror upp till $X$ , där $L(x)=\exp {\left( {\frac {\log x\log \log \log x}{\log \log x}}\right)}$ .

Men inom nuvarande beräkningsintervall (som räkningarna av Carmichael-tal utförda av Pinch upp till 10 ²¹ ), är dessa gissningar ännu inte bekräftade av data.

År 2021 bevisade Daniel Larsen , en 17-årig gymnasieelev från Indiana , en analog till Bertrands postulat för Carmichael-tal som först antogs av Alford, Granville och Pomerance 1994. Med hjälp av tekniker utvecklade av Yitang Zhang och James Maynard för att upprätta resultat rörande små luckor mellan primtal , gav hans arbete det mycket starkare uttalandet att, för alla $\delta >0$ och tillräckligt stora $x$ i termer av $\delta$ , där kommer alltid att vara minst

$\exp {\left({\frac {\log {x}}{(\log \log {x})^{2+ \delta }}}\right)}$

Carmichael-tal mellan $x$ och

$x+{\frac {x}{(\log {x})^{\frac {1}{2+\delta }}}}.$

Generaliseringar

Begreppet Carmichael-tal generaliserar till ett Carmichael-ideal i valfritt talfält K . För alla idealiska primtal som inte är noll ${\mathfrak {p}}$ i ${\displaystyle {\mathcal {O}}_{K}} ,$ har vi ${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {p}})}\equiv \alpha {\bmod {\mathfrak {p}}}} för alla α {\displaystyle$ \ $}$ i ${ \displaystyle {\mathcal {O}}_{K}}$ , där ${\rm {N}}({\mathfrak {p}})$ är normen för det ideala ${\mathfrak {p}}$ . (Detta generaliserar Fermats lilla teorem, att $m^{p}\equiv m{\bmod {p}}$ för alla heltal m när p är primtal.) Kalla ett ideal som inte är noll ${\ displaystyle {\mathfrak {a}}}$ i ${\mathcal {O}}_{K}$ Carmichael om det inte är ett primideal och ${\displaystyle \alpha ^{{\rm {N}}({\mathfrak {a}})}\equiv \alpha {\bmod {\mathfrak {a}}}} för alla α ∈ O K {\displaystyle$ \ $\ mathcal {O}}_{K}}$ , där ${\rm {N}}({\mathfrak {a}})$ är normen för idealet ${\mathfrak { a}}$ . När K är $\mathbf {Q}$ är idealet ${\mathfrak {a}}$ principiellt , och om vi låter a vara dess positiva generator så är idealet ${\ displaystyle {\mathfrak {a}}=(a)}$ är Carmichael exakt när a är ett Carmichael-tal i vanlig mening.

   När K är större än rationalerna är det lätt att skriva ner Carmichael-ideal i ${\mathcal {O}}_{K}$ : för vilket primtal p som helst p som delar sig helt i K , det huvudsakliga idealet $p{\mathcal {O}}_{K}$ är ett Carmichael-ideal. Eftersom oändligt många primtal delar sig helt i valfritt talfält, finns det oändligt många Carmichael-ideal i ${\mathcal {O}}_{K}$ . Till exempel, om p är vilket primtal som helst som är 1 mod 4, är idealet ( p ) i de Gaussiska heltal Z [ i ] ett Carmichael-ideal.

Både primtal och Carmichael-tal uppfyller följande likhet:

$\gcd \left(\sum _{x=1}^{n-1}x^{n-1},n \right)=1.$

Lucas–Carmichael nummer

Huvudartikel: Lucas–Carmichael nummer

Ett positivt sammansatt heltal $n$ är ett Lucas-Carmichael-tal om och endast om $n$ är kvadratfritt , och för alla primtalsdelare $p$ av $n$ , det är sant att $p+1\mid n+1$ . De första Lucas-Carmichael-numren är:

399, 935, 2015, 2915, 4991, 5719, 7055, 8855, 12719, 18095, 20705, 20999, 22847, 29315, 31537, 31037, 5, 0, 5, 5, 6 , 67199, 73535, 76751, 80189, 81719, 88559, 90287, ... (sekvens A006972 i OEIS )

Quasi–Carmichael nummer

Kvasi-Carmichael-tal är kvadratfria sammansatta tal n med egenskapen att för varje primtal p av n delar p + b n + b positivt med b som vilket heltal som helst förutom 0. Om b = −1 är dessa Carmichael-tal, och om b = 1, det här är Lucas–Carmichael-tal. De första Quasi-Carmichael-talen är:

35, 77, 143, 165, 187, 209, 221, 231, 247, 273, 299, 323, 357, 391, 399, 437, 493, 527. , 943, 989, 1015, 1073, 1105, 1147, 1189, 1247, 1271, 1295, 1333, 1517, 1537, 1547, 1591, 1595 , ... IS )

Knödel nummer

Huvudartikel: Knödelnummer

Ett n - Knödeltal för ett givet positivt heltal n är ett sammansatt tal m med egenskapen att varje i < m coprime till m uppfyller $i^{mn}\equiv 1{ \pmod {m}}$ . Fallet n = 1 är Carmichael-tal.

Carmichael-nummer av högre ordning

Carmichael-tal kan generaliseras med begreppen abstrakt algebra .

Ovanstående definition anger att ett sammansatt heltal n är Carmichael just när den n :te makthöjande funktionen p _n från ringen Z _n av heltal modulo n till sig själv är identitetsfunktionen. Identiteten är den enda Z _n - algebraendomorfismen på Z _n så vi kan omformulera definitionen som ber att p n _är en algebraendomorfism av Z _n . Som ovan uppfyller p _n samma egenskap närhelst n är primtal.

Den n _: te effekthöjande funktionen pn är också definierad på vilken Zn _- algebra A som helst . En sats säger att n är primtal om och endast om alla sådana funktioner p _n är algebraendomorfismer.

Mellan dessa två villkor ligger definitionen av Carmichael nummer av ordningen m för varje positivt heltal m som vilket sammansatt tal n som helst så att p _n är en endomorfism på varje Z _n -algebra som kan genereras som Z _n - modul av m element . Carmichael-nummer av ordning 1 är bara de vanliga Carmichael-numren.

En order 2 Carmichael nummer

Enligt Howe är 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331 ett Carmichael nummer för order 2. Denna produkt är lika med 443,372,888,629,441.

Egenskaper

Korselts kriterium kan generaliseras till högre ordningens Carmichael-tal, vilket Howe visar.

Ett heuristiskt argument, som ges i samma artikel, verkar antyda att det finns oändligt många Carmichael-tal av ordningen m , för varje m . Dock är inte ett enda Carmichael-nummer av ordning 3 eller högre känt.

Anteckningar

• Carmichael, RD (1910). "Anmärkning om en ny talteoretisk funktion" . Bulletin från American Mathematical Society . 16 (5): 232–238. doi : 10.1090/s0002-9904-1910-01892-9 .
•   Carmichael, RD (1912). "På sammansatta tal P som uppfyller Fermat-kongruensen ${\displaystyle a^{P-1}\equiv 1{\bmod {P}}} "$ . American Mathematical Monthly . 19 (2): 22–27. doi : 10.2307/2972687 . JSTOR 2972687 .
• Chernick, J. (1939). "Om Fermats enkla teorem" (PDF) . Tjur. Amer. Matematik. Soc . 45 (4): 269–274. doi : 10.1090/S0002-9904-1939-06953-X .
• Korselt, AR (1899). "Problème chinois". L'Intermédiaire des Mathématiciens . 6 : 142–143.
• Löh, G.; Niebuhr, W. (1996). "En ny algoritm för att konstruera stora Carmichael-tal" (PDF) . Matematik. Comp . 65 (214): 823–836. Bibcode : 1996MaCom..65..823L . doi : 10.1090/S0025-5718-96-00692-8 . Arkiverad (PDF) från originalet 2003-04-25.
•   Ribenboim, P. (1989). The Book of Prime Number Records . Springer. ISBN 978-0-387-97042-4 .
• Šimerka, V. (1885). "Zbytky z arithmetické posloupnosti (Om resten av en aritmetisk progression)" . Časopis Pro Pěstování Matematiky a Fysiky . 14 (5): 221–225. doi : 10.21136/CPMF.1885.122245 .

externa länkar

• "Carmichael nummer" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Encyclopedia of Mathematics
• Tabell över Carmichael nummer
• Tabeller över Carmichael-tal med många primtalsfaktorer
• Tabeller över Carmichael-tal under $10^{18}$
• "1729 års matthet" . MathPages.com .
• Weisstein, Eric W. "Carmichael Number" . MathWorld .
• Slutliga svar Modulär aritmetik