Carmichaelin numero

Carmichael-luku on yhdistelmäluku , joka täyttää kongruenssin kaikkien kokonaislukujen koprime -arvoon , toisin sanoen pseudoprime jokaisessa peruskoprimessa . Tällaiset luvut ovat suhteellisen harvinaisia, mutta niitä on äärettömästi, pienin niistä on 561; tällaisten lukujen olemassaolo tekee Fermatin pienen lauseen yksinkertaisuuden ehdon riittämättömäksi eikä salli Fermatin testin käyttöä yleisenä yksinkertaisuuden tarkistamiskeinona. $n$ $b^{{n-1}}\equiv 1{\pmod {n}}$ $b$ $n$ $b$ $n$

Nimetty amerikkalaisen matemaatikon Robert Carmichaelin mukaan .

Yleistä tietoa

Fermat'n pieni lause sanoo, että jos on alkuluku ja on kokonaisluku, joka ei ole jaollinen luvulla , niin se on jaollinen :lla eli . Carmichael-luvut ovat yhdistelmälukuja, ja tämä suhde pätee niihin. Carmichael-lukuja kutsutaan myös ehdottoman pseudoalkuluvuiksi Fermat-luvuiksi, koska ne ovat pseudoprime-Fermat-lukuja jokaisessa niiden kanssa. $n$ $b$ $n$ $b^{{n-1}}-1$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Carmichael-lukujen olemassaolo tekee Fermat-primaliteettitestistä vähemmän tehokkaan alkulukujen havaitsemisessa verrattuna esimerkiksi tiukempaan Nightingale-Strassen-testiin , joka tunnistaa nämä luvut yhdistelmäluvuiksi. Carmichaelin lukumäärän kasvaessa niistä tulee harvinaisempia. Esimerkiksi välillä 1-1021 niitä on 20 138 200 (noin yksi 50 biljoonasta numerosta). On kuitenkin todistettu, että Carmichael-lukuja on äärettömän monta [1] .

Historia

Ensimmäinen henkilö, joka löysi numeeriset ominaisuudet, joista myöhemmin tuli Carmichaelin lukujen ominaisuus, oli Alvin Corselt , joka todisti vuonna 1899 kokonaislukulauseen, joka vastaa Fermatin pienen lauseen käänteisiä ehtoja eli kokonaislukuja , joille se pätee kaikille kokonaisluvuille : yhdistelmäluku on Carmichael-luku silloin ja vain jos se on neliötön ja jokaiselle luvun alkujakajalle luku jakaa luvun [2] . $n$ $b^{{n}}\equiv b{\pmod {n}}$ $b$ $n$ $n$ $s$ $n$ $p-1$ $n-1$

Corseltin lauseen todiste [2] .

Olkoon tämä kaikille kokonaisluvuille . Todistetaan ensin, että luvun on oltava neliötön. Oletetaan, että näin ei ole, ja ( jakaa ) jollekin kokonaisluvulle . Anna sitten . Koska tämä relaatio on tosi modulo , eli mikä on ristiriidassa lausekkeen kanssa . Siten luku on vapaa neliöistä. Olkoon nyt alkujakaja . Tiedetään, että jäännösrenkaan multiplikatiivinen ryhmä modulo , jossa on alkuluku, on syklinen järjestyksen ryhmä . Antaa olla kokonaisluku sellainen, että se on ryhmän generaattori . Koska , Sitten meillä on , ja koska ja ovat koprime-lukuja, sitten . Koska ryhmän primitiivisen elementin järjestys on , tästä seuraa, että . $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$ $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\mid n-1$

Toisaalta oletetaan, että se on vapaa neliöistä ja mistä tahansa alkuluvusta . Antaa olla jokin alkuluku jakamalla Ja numero on kokonaisluku. $n$ $p-1\mid n-1$ $p | n$ $s$ $n$ $b$

Se seuraa Fermat's Little Theorem, että jos on alkuluku ja on kokonaisluku, niin minkä tahansa positiivisen kokonaisluvun sellainen, että . (Anna , missä on positiivinen kokonaisluku. Koska , siis ) $s$ $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))$

Sitten tietyssä tapauksessa meillä on, joka on jaollinen millä tahansa luvun alkujakajalla , koska se on vapaa neliöistä, niin se on jaollinen : llä , eli . Siten Corseltin lause on todistettu. $k = n$ $b^n-b$ $n$ $n$ $b^n-b$ $n$ $b^{{n}}\equiv b{\pmod {n}}$

Corselt jätti avoimeksi kysymyksen yhdistelmälukujen löytämisestä, jotka täyttävät tämän kriteerin. Vuonna 1910 Carmichael muotoili kriteerin, joka olennaisesti vastaa Corseltin kriteeriä, ja antoi esimerkin yhdistelmäluvusta , jolle se täyttyy - . Tämä luku on kertoimella 561 = 3 11 17, joten siinä ei ole neliöitä, mutta se on jaollinen 2:lla, 10:llä ja 16:lla. Sen jälkeen kaikkia vastaesimerkkejä kutsuttiin Carmichael-luvuiksi. $n$ $n=561$ $561-1=560$

Erityisesti Corseltin lauseesta seuraa, että kaikki Carmichael-luvut ovat parittomia, koska jokaisella parillisella neliöttömällä yhdistelmäluvulla on ainakin yksi pariton alkujakaja, joten jaollisuus tarkoittaa, että parillinen luku jakaa parittoman luvun, mikä on mahdotonta. $p-1\mid n-1$

Vuonna 1939 John Chernick osoitti lauseen, jota voidaan käyttää Carmichael-lukujen osajoukon muodostamiseen: jos , , ovat alkulukuja yhdelle luonnolliselle luvulle , niin niiden tulo on Carmichael-luku [2] . Tämä ehto voi täyttyä vain, jos luku päättyy numeroihin 0, 1, 5 tai 6 kannassa 10, eli se on verrattavissa 0:aan tai 1:een modulo 5. Esimerkiksi kertoimet ovat , ja vastaavasti , ja heidän tuotteensa antaa Carmichaelin numeron 1729 . $6m+1$ $12m+1$ $18m+1$ $m$ $M_{3}(m)=(6m+1)(12m+1)(18m+1)$ $m$ $m$ $m = 1$ $7$ $13$ $19$

Chernikin tapaa löytää Carmichaelin numerot voidaan laajentaa useilla tekijöillä : $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

edellyttäen, että kaikki tekijät ovat alkulukuja ja jaollisia . $m$ $2^{{k-4}}$

Carmichael ilmaisi hypoteesin tällaisten lukujen äärettömyydestä vuonna 1912, Chernikin lause lisäsi spekulatiivisesti sen toteutumisen todennäköisyyttä; myöhemmin Pal Erdős perusti heuristisesti Carmichaelin lukujen äärettömyyden. Kuitenkin vasta vuonna 1992 [2] William Alford, Andrew Granville ja Carl Pomerance [1] vahvistivat tämän väitteen tiukasti , tarkemmin sanottuna: todistettiin, että Carmichael-luvut ovat välillä 1 ja riittävän suuri . $n$ $n^{{2/7}}$

Vuonna 1992 Günter Le ja Wolfgang Niebuhr ehdottivat uutta algoritmia suurten Carmichael-lukujen rakentamiseen: he onnistuivat löytämään luvun, joka saatiin kertomalla 1 101 518 alkulukua; tämä numero sisältää 16 142 049 numeroa [3] .

Ominaisuudet

Bigerin ja Duparcin lauseet

Vuonna 1956 Biger osoitti, että jos alkulukuja varten , ja suhde ja on Carmichaelin luku, sitten ja . Näin ollen Carmichael-lukujen lukumäärä, joka saadaan kolmen alkutekijän tulolla, joista yksi on tietysti tiedossa. $s$ $q$ $r$ $p<q<r$ $pqr$ $q<2p^{2}$ $r<p^{3}$

Duparc myöhemmin yleisti tämän tuloksen osoittaakseen, että jos on Carmichael-luku, missä ja ovat alkulukuja, sitten ja . Siksi on korkeintaan äärellinen määrä Carmichael-lukuja, joilla on kaikki paitsi kaksi määriteltyä tekijää. $n=mqr$ $q$ $r$ $q<2m^{2}$ $r<m^{3}$

Tapaus = 1 osoittaa, että mikä tahansa Carmichael-luku sisältää vähintään 3 alkutekijää, tämän päätelmän teki ensin Carmichael itse. $m$

Ensisijaiset tekijät

Ensimmäisten Carmichael-lukujen alkutekijät ovat seuraavat:

{\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}}

Carmichael-luvuilla on vähintään kolme positiivista alkutekijää. Ensimmäiset Carmichael-luvut alkutekijöillä [4] : $k = 3,4,5,\lpistettä$

k
3	$561=3\cdot 11\cdot 17$
neljä	$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$
kahdeksan	$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$

Ensimmäiset Carmichael-luvut neljällä alkutekijällä [5] :

i
yksi	$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$
neljä	$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$
kahdeksan	$188461=7\cdot 13\cdot 19\cdot 109$
9	$278545=5\cdot 17\cdot 29\cdot 113$
kymmenen	$340561=13\cdot 17\cdot 23\cdot 67$

Jakelu

Seuraavassa taulukossa näkyy Carmichael-lukujen lukumäärä, joka on pienempi tai yhtä suuri kuin , joka annetaan kymmenen potenssina: [6] $C(X)$ $X$ $n$

$n$	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen	yksitoista	12	13	neljätoista	viisitoista	16
$C(10^{n})$	0	0	yksi	7	16	43	105	255	646	1547	3605	8241	19279	44706	105212	246683

Vuonna 1953 Walter Knödel osoitti, että:

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

joillekin jatkuvalle . $k_{1}$

Antaa merkitsee Carmichael-lukujen määrää pienempiä kuin . Erdős todisti sen vuonna 1956 $C(X)$ $X$

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

joillekin jatkuvalle . Samalla myös todistettiin [1] , että Carmichael-lukuja on äärettömän monta, eli . $k_{2}$ $\lim _{{X\to \infty }}C(X)=\infty$

Seuraavassa taulukossa on esitetty vakion k likimääräiset vähimmäisarvot arvoille X = 10 n eri n :ille :

$n$	neljä	6	kahdeksan	kymmenen	12	neljätoista	16	kahdeksantoista	kaksikymmentä	21
k	2.19547	1,97946	1,90495	1,86870	1,86377	1,86293	1,86406	1,86522	1,86598	1,86619

Yksittäisten numeroiden harvinaiset ominaisuudet

Toinen Carmichael-luku (1105) voidaan esittää kahden neliön summana useammilla tavoilla kuin mikään pienempi luku.

Kolmas Carmichael-luku ( 1729 ) on Ramanujan-Hardyn luku (pienin luku, joka voidaan esittää kahden kuution summana kahdella tavalla).

Muistiinpanot

↑ 1 2 3 W. R. Alford, A. Granville, C. Pomerance. Carmichael-lukuja on äärettömän monta // Annals of Mathematics : Journal . - 1994. - Voi. 139 . - s. 703-722 . - doi : 10.2307/2118576 .
↑ 1 2 3 4 C. Pomerance. Carmichael-luvut (uuspr.) // Nieuw Arch. Wisk.. - 1993. - S. 199-209 .
↑ G Loh, W. Niebuhr. Uusi algoritmi suurten Carmichael-lukujen rakentamiseen // Math . Comp. : päiväkirja. - 1996. - Voi. 65 , no. 214 . - s. 823-836 .
↑ OEIS - sekvenssi A006931 _
↑ OEIS - sekvenssi A074379 _
↑ Richard Pinch. "Carmichaelin numerot jopa 10^21" (2007). (määrätön)

Sanakirjat ja tietosanakirjat	Britannica (verkossa)