Carmichael szám

A Carmichael-szám egy olyan összetett szám , amely kielégíti a kongruenciát az összes egész számhoz , más szóval egy pszeudoprím minden bázis másodprímében . Az ilyen számok viszonylag ritkák, de számuk végtelen, közülük a legkisebb az 561; az ilyen számok megléte elégtelenné teszi a Fermat-féle kis tétel egyszerűségére vonatkozó feltételt , és nem teszi lehetővé a Fermat-próba alkalmazását az egyszerűség ellenőrzésének univerzális eszközeként. $n$ $b^{{n-1}}\equiv 1{\pmod {n}}$ $b$ $n$ $b$ $n$

Nevét Robert Carmichael amerikai matematikusról kapta .

Általános információk

Fermat kis tétele kimondja, hogy ha egy prímszám, és olyan egész szám, amely nem osztható -vel , akkor osztható -vel , azaz . A Carmichael-számok összetettek, és ez az összefüggés érvényes rájuk. A Carmichael-számokat abszolút pszeudoprím Fermat-számoknak is nevezik, mivel ezek álprím Fermat- számok minden velük együtt járó prímbázisban. $n$ $b$ $n$ $b^{{n-1}}-1$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

A Carmichael-számok megléte miatt a Fermat primalitásteszt kevésbé hatékony a prímszámok kimutatásában, mint például a szigorúbb Nightingale-Strassen teszt , amely ezeket a számokat összetettként ismeri fel. Carmichael számának növekedésével egyre ritkábbak lesznek. Például az 1-től 1021-ig terjedő tartományban 20 138 200 van belőlük (körülbelül egy az 50 billió számból). Azonban bebizonyosodott, hogy végtelenül sok Carmichael-szám létezik [1] .

Történelem

Az első ember, aki felfedezte azokat a numerikus tulajdonságokat, amelyek később a Carmichael-számok jellemzőivé váltak, Alvin Corselt volt , aki 1899 -ben bebizonyította a Fermat-féle kis tétel megfordítási feltételeivel ekvivalens egész számtételt, azaz egész számokra , amelyekre ez bármely egész számra érvényes. : az összetett szám akkor és csak akkor Carmichael -szám, ha négyzetmentes, és a szám minden prímosztójára a szám osztja a számot [2] . $n$ $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $n$ $p$ $n$ $p-1$ $n-1$

Corselt tételének bizonyítása [2] .

Legyen ez az összes egész számra . Először bizonyítsuk be, hogy a számnak négyzetmentesnek kell lennie. Tegyük fel, hogy ez nem így van, és ( oszt ) valamilyen egész számra . Akkor hagyd . Mivel , akkor ez a reláció igaz modulo , vagyis ami ellentmond a kifejezésnek . Így a szám mentes a négyzetektől. Legyen most főosztója . Ismeretes, hogy a modulo maradékok gyűrűjének multiplikatív csoportja , ahol prím, egy ciklikus rendű csoport . Legyen egy egész szám, amely a csoport generátora . Mivel , akkor van , és mivel és koprímszámok, akkor . Mivel egy csoportban egy primitív elem sorrendje , ebből következik, hogy . $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$ $p$ $n$ $(\mathbb{Z}/p\mathbb{Z})^*$ $p$ $p$ $p-1$ $b$ $b\pmod{p}$ $(\mathbb{Z}/p\mathbb{Z})^*$ $b^{{n}}\equiv b{\pmod {n}}$ $b^{n}\equiv b\pmod{p}$ $b$ $p$ $b^{n-1}\equiv 1\pmod{p}$ $b\pmod{p}$ $(\mathbb{Z}/p\mathbb{Z})^*$ $p-1$ $p-1\mid n-1$

Másrészt tegyük fel, hogy ez mentes a négyzetektől és bármilyen prímszámra . Legyen valami osztó prímszám , a szám pedig egész szám. $n$ $p-1\mid n-1$ $p | n$ $p$ $n$ $b$

Fermat kis tételéből következik, hogy ha prímszám és egész szám, akkor minden olyan pozitív egészre , amelyre . (Legyen , ahol pozitív egész szám. Mivel , tehát ) $p$ $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}}$

Ekkor egy adott esetre van, amely osztható a szám tetszőleges prímosztójával , mivel mentes a négyzetektől, akkor osztható -val , azaz . Így Corselt tétele bizonyítást nyer. $k=n$ $b^n-b$ $n$ $n$ $b^n-b$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Corselt nyitva hagyta az összetett számok megtalálásának kérdését, amelyek megfelelnek ennek a kritériumnak. 1910 -ben Carmichael megfogalmazott egy kritériumot, amely lényegében egybeesik a Corselt-kritériummal, és példát adott egy összetett számra , amelyre ez teljesül - . Ez a szám 561 = 3 11 17 faktorszámú, ezért mentes a négyzetektől, miközben osztható 2-vel, 10-gyel és 16-tal. Ezt követően az összes ellenpéldát Carmichael-számnak nevezték. $n$ $n=561$ $561-1=560$

Corselt tételéből különösen az következik, hogy minden Carmichael-szám páratlan, mivel minden páros négyzet nélküli összetett számnak van legalább egy páratlan prímosztója, így az oszthatóság azt jelenti, hogy páros szám eloszt egy páratlan számot, ami lehetetlen. $p-1\mid n-1$

1939 -ben John Chernick bebizonyított egy tételt, amellyel a Carmichael-számok egy részhalmaza megszerkeszthető: ha , , prímszámok egy természetes , akkor a szorzatuk egy Carmichael-szám [2] . Ez a feltétel csak akkor teljesülhet, ha a szám a 10-es bázisban 0, 1, 5 vagy 6 számjegyekkel végződik, azaz összevethető 0 vagy 1 modulo 5-tel. Például a , illetve , faktorokra szorzatuk pedig az 1729-es Carmichael- számot adja . $6m+1$ $12m+1$ $18m+1$ $m$ $M_{3}(m)=(6m+1)(12m+1)(18m+1)$ $m$ $m$ $m=1$ $7$ $13$ $19$

Chernik módszere Carmichael számainak megtalálására számos tényezővel bővíthető : $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

feltéve, hogy minden tényező prím és osztható -vel . $m$ $2^{{k-4}}$

Az ilyen számok végtelenségére vonatkozó hipotézist Carmichael fogalmazta meg 1912-ben, Chernik tétele spekulatív módon növelte a megvalósítás valószínűségét; később Erdős Pál heurisztikusan alátámasztotta a Carmichael-számok végtelenségét. Ezt az állítást azonban csak 1992 -ben [2] igazolta szigorúan William Alford, Andrew Granville és Carl Pomerance [1] , pontosabban: bebizonyosodott, hogy vannak Carmichael-számok 1 és kellően nagy között . $n$ $n^{{2/7}}$

1992 -ben Günter Le és Wolfgang Niebuhr új algoritmust javasolt a nagy Carmichael-számok megszerkesztésére: sikerült megtalálniuk az 1 101 518 prímszám szorzásával kapott számot ; ez a szám 16 142 049 számjegyet tartalmaz [3] .

Tulajdonságok

Biger és Duparc tételei

1956-ban Biger bebizonyította, hogy ha prímszámokra , és a és a reláció Carmichael-szám, akkor és . Így három prímtényező szorzatával kapott Carmichael-számok száma, amelyek közül az egyik természetesen ismert. $p$ $q$ $r$ $p<q<r$ $pqr$ $q<2p^{2}$ $r<p^{3}$

Duparc később általánosította ezt az eredményt annak bemutatására, hogy ha egy Carmichael-szám, ahol és a prímek, akkor és . Ezért legfeljebb véges számú Carmichael-szám létezik, amelyeknek két kivételével mindegyik definiált tényezője van. $n=mqr$ $q$ $r$ $q<2m^{2}$ $r<m^{3}$

Az 1-es eset azt mutatja, hogy bármely Carmichael-szám legalább 3 prímtényezőt tartalmaz, ezt a következtetést először maga Carmichael vonta le. $m$

Prime factorizations

Az első néhány Carmichael-szám prímtényezői a következők:

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

A Carmichael-számoknak legalább három pozitív prímtényezője van. Az első prímtényezős Carmichael-számok [4] : $k=3,4,5,\lpont$

k
3	$561=3\cdot 11\cdot 17$
négy	$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$
nyolc	$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$

Az első Carmichael-számok négy prímtényezővel [5] :

én
egy	$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$
négy	$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$
nyolc	$188461=7\cdot 13\cdot 19\cdot 109$
9	$278545=5\cdot 17\cdot 29\cdot 113$
tíz	$340561=13\cdot 17\cdot 23\cdot 67$

Elosztás

A következő táblázat a -nál kisebb vagy egyenlő Carmichael-számokat mutatja, amely tíz hatványaként van megadva : [6] $C(X)$ $x$ $n$

$n$	egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt	16
$C(10^{n})$	0	0	egy	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683

1953-ban Walter Knödel bebizonyította, hogy:

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

valami állandó . $k_{1}$

Jelölje a -nál kisebb Carmichael-számok számát . Erdős 1956 - ban bebizonyította $C(X)$ $x$

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

valami állandó . Ugyanakkor az is bebizonyosodott [1] , hogy végtelenül sok Carmichael-szám van, azaz . $k_{2}$ $\lim _{{X\to \infty }}C(X)=\infty$

A következő táblázat a k konstans hozzávetőleges minimális értékeit mutatja X = 10 n értékek esetén különböző n értékekhez :

$n$	négy	6	nyolc	tíz	12	tizennégy	16	tizennyolc	húsz	21
k	2.19547	1,97946	1,90495	1,86870	1,86377	1,86293	1.86406	1,86522	1,86598	1,86619

Az egyes számok ritka tulajdonságai

A második Carmichael-szám (1105) többféleképpen ábrázolható két négyzet összegeként, mint bármely kisebb szám.

A harmadik Carmichael-szám ( 1729 ) a Ramanujan-Hardy- szám (a legkisebb szám, amely két kocka összegeként kétféleképpen ábrázolható).

Jegyzetek

↑ 1 2 3 W. R. Alford, A. Granville, C. Pomerance. Végtelenül sok Carmichael-szám van // Annals of Mathematics : folyóirat . - 1994. - 1. évf. 139 . - P. 703-722 . - doi : 10.2307/2118576 .
↑ 1 2 3 4 C. Pomerance. Carmichael-számok (neopr.) // Nieuw Arch. Wisk.. - 1993. - S. 199-209 .
↑ G Loh, W. Niebuhr. Egy új algoritmus nagy Carmichael-számok létrehozására // Math . Összeg. : folyóirat. - 1996. - 1. évf. 65 , sz. 214 . - P. 823-836 .
↑ OEIS szekvencia A006931 _
↑ OEIS szekvencia A074379 _
↑ Richard Pinch. "A Carmichael-számok 10^21-ig" (2007). (határozatlan)

Szótárak és enciklopédiák	Britannica (online)