Carmichaelovo číslo

Carmichaelovo číslo je složené číslo , které splňuje shodu všech celých čísel coprime to , jinými slovy pseudoprvo v každém základním coprime to . Taková čísla jsou relativně vzácná, ale jejich počet je nekonečný, nejmenší z nich je 561; existence takových čísel činí podmínku jednoduchosti Fermatovy malé věty nedostatečnou a neumožňuje použití Fermatova testu jako univerzálního prostředku pro kontrolu jednoduchosti. $n$ $b^{{n-1}}\ekviv 1{\pmod {n}}$ $b$ $n$ $b$ $n$

Pojmenován po americkém matematikovi Robertu Carmichaelovi .

Obecné informace

Fermatova malá věta říká, že jestliže je prvočíslo a je celé číslo, které není dělitelné , pak je dělitelné , tedy . Carmichaelova čísla jsou složená a tento vztah pro ně platí. Carmichaelova čísla se také nazývají absolutně pseudoprvočísla Fermatova čísla, protože jsou to pseudoprvní Fermatova čísla v každém spoluprvočíslém základu s nimi. $n$ $b$ $n$ $b^{{n-1}}-1$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Existence Carmichaelových čísel činí Fermatův test primality méně účinným při odhalování prvočísel, ve srovnání například s přísnějším Nightingale-Strassenovým testem , který tato čísla rozpoznává jako složená. Jak se Carmichaelovy počty zvyšují, stávají se vzácnějšími. Například v rozmezí od 1 do 1021 jich je 20 138 200 (asi jedno z 50 bilionů čísel). Bylo však dokázáno, že Carmichaelových čísel je nekonečně mnoho [1] .

Historie

Prvním člověkem, který objevil numerické vlastnosti, které se později staly charakteristikou Carmichaelových čísel, byl Alvin Corselt , který v roce 1899 dokázal, že celočíselná věta je ekvivalentní reverzním podmínkám Fermatovy malé věty, tedy pro celá čísla , pro která platí pro všechna celá čísla . : složené číslo je Carmichaelovo číslo právě tehdy, je-li bez čtverce a pro každého prvočíselného čísla číslo dělí číslo [2] . $n$ $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $n$ $p$ $n$ $p-1$ $n-1$

Důkaz Corseltovy věty [2] .

Nechte to pro všechna celá čísla . Nejprve dokažme, že číslo musí být bez čtverců. Předpokládejme , že tomu tak není a ( dělí ) pro nějaké celé číslo . Nechte tedy . Protože , pak je tento vztah pravdivý modulo , to znamená , že je v rozporu s výrazem . Číslo je tedy bez čtverců. Nechť je nyní hlavním dělitelem . Je známo, že multiplikativní skupina kruhu zbytků modulo , kde je prvočíslo, je cyklická skupina řádu . Dovolit být celé číslo takové, že je generátor skupiny . Od , pak máme , a od a jsou prvočísla, pak . Protože pořadí primitivního prvku ve skupině je , vyplývá z toho, že . $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $k^{2}\mid n$ $k^{2}$ $n$ $k>1$ $b=k$ $k^{n}\ekviv 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}\ekviv 1\pmod{p}$ $b\pmod{p}$ $(\mathbb{Z}/p\mathbb{Z})^*$ $p-1$ $p-1\mid n-1$

Na druhou stranu předpokládejme, že je bez čtverců a pro jakékoli prvočíslo . Dovolit být nějaké prvočíslo dělení a číslo je celé číslo. $n$ $p-1\mid n-1$ $p | n$ $p$ $n$ $b$

Z Fermatovy Malé věty vyplývá, že jestliže je prvočíslo a je celé číslo, pak pro jakékoli kladné celé číslo takové, že . (Nechť , kde je kladné celé číslo. Protože , tedy ) $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}}$

Pak pro konkrétní případ máme, že je dělitelné libovolným prvočíslem dělitele čísla , protože je bez druhých mocnin, pak je dělitelné , tedy . Tím je Corseltova věta dokázána. $k=n$ $b^n-b$ $n$ $n$ $b^n-b$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Corselt nechal otevřenou otázku hledání složených čísel, která splňují toto kritérium. V roce 1910 Carmichael formuloval kritérium, které se v podstatě shoduje s Corseltovým kritériem, a uvedl příklad složeného čísla , pro které je splněno - . Toto číslo je faktorizováno jako 561 = 3 11 17, a proto je bez druhých mocnin, zatímco je dělitelné 2, 10 a 16. Poté byly všechny protipříklady nazývány Carmichaelovými čísly. $n$ $n=561$ $561-1=560$

Zejména z Corseltovy věty vyplývá, že všechna Carmichaelova čísla jsou lichá, protože každé sudé složené číslo bez čtverců má alespoň jednoho lichého prvočísla, a tak dělitelnost znamená, že sudé číslo dělí liché, což je nemožné. $p-1\mid n-1$

V roce 1939 John Chernick dokázal větu, kterou lze použít ke konstrukci podmnožiny Carmichaelových čísel: jestliže , , jsou prvočísla pro jeden přirozený , pak jejich součin je Carmichaelovo číslo [2] . Tato podmínka může být splněna pouze v případě, že číslo končí číslicemi 0, 1, 5 nebo 6 v základu 10, to znamená, že je srovnatelné s 0 nebo 1 modulo 5. Například pro faktory jsou , a , resp . a jejich produkt dává Carmichaelovo číslo 1729 . $6m+1$ $12m+1$ $18m+1$ $m$ $M_{3}(m)=(6m+1)(12m+1)(18m+1)$ $m$ $m$ $m=1$ $7$ $13$ $19$

Chernikův způsob hledání Carmichaelových čísel lze rozšířit o řadu faktorů : $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

za předpokladu, že všechny faktory jsou prvočísla a dělitelné . $m$ $2^{{k-4}}$

Hypotézu o nekonečnosti takových čísel vyslovil Carmichael v roce 1912, Chernikova věta spekulativně zvýšila pravděpodobnost jejího provedení; později Pal Erdős heuristicky doložil nekonečnost Carmichaelových čísel. Nicméně, to nebylo dokud ne 1992 [2] že toto tvrzení bylo přísně dokázáno Williamem Alfordem, Andrew Granville , a Carl Pomerance [1] , přesněji: to bylo dokázané, že tam jsou Carmichael čísla mezi 1 a dostatečně velká . $n$ $n^{{2/7}}$

V roce 1992 Günter Le a Wolfgang Niebuhr navrhli nový algoritmus pro konstrukci velkých Carmichaelových čísel: podařilo se jim najít číslo získané vynásobením 1 101 518 prvočísel; toto číslo obsahuje 16 142 049 číslic [3] .

Vlastnosti

Bigerova a Duparcova věta

V roce 1956 Biger dokázal, že jestliže pro prvočísla a vztah a je Carmichaelovo číslo, pak a . Tedy počet Carmichaelových čísel získaných součinem tří prvočinitelů, z nichž jeden je samozřejmě znám. $p$ $q$ $r$ $p<q<r$ $pqr$ $q<2p^{2}$ $r<p^{3}$

Duparc později tento výsledek zobecnil, aby ukázal, že jestliže je Carmichaelovo číslo, kde a jsou prvočísla, pak a . Proto existuje nanejvýš konečný počet Carmichaelových čísel se všemi definovanými faktory kromě dvou. $n=mqr$ $q$ $r$ $q<2m^{2}$ $r<m^{3}$

Případ = 1 ukazuje, že jakékoli Carmichaelovo číslo obsahuje alespoň 3 prvočísla, tento závěr poprvé učinil sám Carmichael. $m$

Prvotřídní faktorizace

Prvočíselné rozklady prvních několika Carmichaelových čísel jsou následující:

{\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\polovina 1725),\\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;282\mid ;30\mid 2820),\\6601=7\cdot 23\cdot 41&\qquad (6\mid 6600;22\mid 6600;40\mid 6600),\\8911=7\cdot 19&\qdqua 67 (6\mid 8910;18\mid 8910;66\mid 8910).\end{aligned}}

Carmichaelova čísla mají alespoň tři kladné prvočinitele. První Carmichaelova čísla s prvočiniteli [4] : $k=3,4,5,\ldots$

k
3	$561=3\cdot 11\cdot 17$
čtyři	$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$
osm	$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$

První Carmichaelova čísla se čtyřmi prvočísly [5] :

i
jeden	$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$
čtyři	$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$
osm	$188461=7\cdot 13\cdot 19\cdot 109$
9	$278545=5\cdot 17\cdot 29\cdot 113$
deset	$340561=13\cdot 17\cdot 23\cdot 67$

Distribuce

Následující tabulka ukazuje počet Carmichaelových čísel menších nebo rovných , což je udáno jako mocnina deseti: [6] $C(X)$ $X$ $n$

$n$	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16
$C(10^{n})$	0	0	jeden	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683

V roce 1953 Walter Knödel dokázal, že:

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

za nějakou stálou . $k_{1}$

Označme počet Carmichaelových čísel menší než . Erdős to v roce 1956 dokázal $C(X)$ $X$

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

za nějakou stálou . Zároveň bylo také prokázáno [1] , že Carmichaelových čísel je nekonečně mnoho, tedy . $k_{2}$ $\lim _{{X\to \infty }}C(X)=\infty$

Následující tabulka ukazuje přibližné minimální hodnoty konstanty k pro hodnoty X = 10 n pro různé n :

$n$	čtyři	6	osm	deset	12	čtrnáct	16	osmnáct	dvacet	21
k	2,19547	1,97946	1,90495	1,86870	1,86377	1,86293	1,86406	1,86522	1,86598	1,86619

Vzácné vlastnosti jednotlivých čísel

Druhé Carmichaelovo číslo (1105) může být reprezentováno jako součet dvou čtverců více způsoby než jakékoli menší číslo.

Třetí Carmichaelovo číslo ( 1729 ) je Ramanujanovo-Hardyho číslo (nejmenší číslo, které lze vyjádřit jako součet dvou kostek dvěma způsoby).

Poznámky

↑ 1 2 3 W. R. Alford, A. Granville, C. Pomerance. Existuje nekonečně mnoho Carmichaelových čísel // Annals of Mathematics : journal . - 1994. - Sv. 139 . - str. 703-722 . - doi : 10.2307/2118576 .
↑ 1 2 3 4 C. Pomerance. Carmichael čísla (neopr.) // Nieuw Arch. Wisk.. - 1993. - S. 199-209 .
↑ G Loh, W. Niebuhr. Nový algoritmus pro konstrukci velkých Carmichaelových čísel // Math . Comp. : deník. - 1996. - Sv. 65 , č. 214 . - S. 823-836 .
↑ OEIS sekvence A006931 _
↑ OEIS sekvence A074379 _
↑ Richard Pinch. „Carmichael čísla až 10^21“ (2007). (neurčitý)

Slovníky a encyklopedie	Britannica (online)