Carmichael-toiminto

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 1. tammikuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Carmichael-funktio on lukuteoreettinen funktio , joka on yhtä suuri kuin pienin eksponentti siten, että $\lambda (n)$ $m$

a^{m}\equiv 1{\pmod {n))

kaikille kokonaisluvuille koprime ja modulo . Ryhmäteorian kielellä on eksponentti multiplikatiiviselle jäännösryhmälle modulo . $a$ $n$ $\lambda (n)$ $n$

Tässä on taulukko funktiosekvenssin A002322 ensimmäisistä 36 arvosta OEIS :ssä verrattuna Euler-funktion arvoihin . (eri arvot on korostettu lihavoidulla) $\lambda (n)$ $\varphi$

n	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen	yksitoista	12	13	neljätoista	viisitoista	16	17	kahdeksantoista	19	kaksikymmentä	21	22	23	24	25	26	27	28	29	kolmekymmentä	31	32	33	34	35	36
$\lambda (n)$	yksi	yksi	2	2	neljä	2	6	2	6	neljä	kymmenen	2	12	6	neljä	neljä	16	6	kahdeksantoista	neljä	6	kymmenen	22	2	kaksikymmentä	12	kahdeksantoista	6	28	neljä	kolmekymmentä	kahdeksan	kymmenen	16	12	6
$\varphi (n)$	yksi	yksi	2	2	neljä	2	6	neljä	6	neljä	kymmenen	neljä	12	6	kahdeksan	kahdeksan	16	6	kahdeksantoista	kahdeksan	12	kymmenen	22	kahdeksan	kaksikymmentä	12	kahdeksantoista	12	28	kahdeksan	kolmekymmentä	16	kaksikymmentä	16	24	12

Esimerkki

1,3,5,7 ovat kaikki lukuja pienempiä kuin 8 ja suhteellisen alkulukuja siihen, joten Carmichael-funktio on 2. Euler-funktio on 4, koska listassa 1,3,5,7 on tasan 4 numeroa. $1^{2}\equiv 1{\pmod {8));\ 3^{2}=9\equiv 1{\pmod {8));\ 5^{2}=25\equiv 1{ \pmod {8));\ 7^{2}=49\equiv 1{\pmod {8}}$ $\lambda (8)$ $\varphi (8)$

Carmichaelin lause

Carmichael-funktio parittomien alkulukujen potenssien sekä lukujen 2 ja 4 osalta on yhtä suuri kuin Euler-funktio ; kun potenssit kaksi ovat suurempia kuin 4, se on yhtä suuri kuin puolet Euler-funktiosta: $\lambda (n)$ $\varphi (n)$

\lambda (n)={\begin{cases}\;\;\varphi (n)&{\text{if ))n=2,3,4,5,6,7,9,10, 11,13,14,17,18,19,22,23,25,26,27,29\pisteet \\{\frac {1}{2}}\varphi (n)&{\text{if }} n=8,16,32,64,128,256\pisteet \end{cases}}

Alkulukujen potenssien Euler-funktio on

\varphi (p^{k})=p^{k-1}(p-1).\;

Aritmeettisen peruslauseen mukaan mikä tahansa voidaan esittää muodossa $n>1$

n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{s}^{a_{s}}

missä ovat alkuluvut ja kaikki . ${\displaystyle p_{1}<p_{2}<\dots <p_{s))$ $a_{i}>0$

Yleisessä tapauksessa on pienin yhteinen kerrannainen kaikista tekijöihin sisällytettyjen alkulukujen tarkkojen potenssien osalta : $\lambda (n)$ $\lambda (p_{i}^{a_{i)))$ $n$

\lambda (n)=\operaattorinimi {lcm} [\lambda (p_{1}^{a_{1))),\;\lambda (p_{2}^{a_{2))),\ pisteet ,\lambda (p_{s}^{a_{s}})].

Carmichaelin lause

Jos koprime, niin $a,n$

a^{\lambda (n)}\equiv 1{\pmod {n))

Toisin sanoen Carmichaelin lause sanoo, että yllä olevan kaavan avulla määritelty funktio itse asiassa täyttää Carmichaelin funktion määritelmän. Tämä lause voidaan todistaa käyttämällä primitiivisiä juuria ja kiinalaista jäännöslausetta .

Todiste

Todistakaamme ensin, että kaikille koprime c , . $a$ $n$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Fermatin pienen lauseen mukaan , jokaiselle yksinkertaiselle moduulille ja mille tahansa moduulin koprimelle, meillä on . $s$ $a$ $a^{p-1}=1+hp$

Jos , niin ${\displaystyle a^{p^{k-1}(p-1)}=1+hp^{k))$

$a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+h^{p}pp^{k}+\pisteet =1+ h_{0}p^{k+1}$

Sitten matemaattisen induktion menetelmällä saamme sen kaikille . $a$ ${\displaystyle a^{p^{k-1}(p-1)}=a^{\lambda (p^{k})}\equiv 1{\pmod {p^{k))))$

Moduulissa 2 suhde on jonkin verran vahvempi:

Jos outoa, niin . $a$ $a=1+2t$

Sitten . ${\displaystyle a^{2}=1+4h(t+1)=1+8C_{t+1}^{2))$

Seuraavaksi jos , niin sitten $a^{2^{k-2}}=1+2^{k}h$

$a^{2^{k-1}}=(1+2^{k}h)^{2}=1+2^{k+1}(t+2^{k-1}t ^{2})$

Sitten, matemaattinen induktio, saamme, että kaikki outoa varten , On totta, että . $a$ $k\geqslant 3$ ${\displaystyle a^{2^{k-2}}=a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k))))$

Lopuksi, jos ja on coprime kanssa , sitten ja , niin ja ja sitten . $n=2^{k}p_{1}^{a_{1}}\dots p_{s}^{a_{s}}$ $a$ $n$ $a^{\lambda (p_{j}^{a_{j)))}\equiv 1{\pmod {p_{j}^{a_{j))))$ ${\displaystyle a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k))))$ $a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{a_{j))))$ ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {2^{k))))$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Huomaa myös, että minkään väitettä ei voida vahvistaa: eksponentti on minimi, jolle . Tämä on helposti todistettavissa ristiriitaisesti. $a$ $\lambda (n)$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Todellakin, olkoon alkuluku sellainen, että kaikille . Koska , Sitten jakaa joitakin , Eli kaikille . Tämä on kuitenkin ristiriidassa sen tosiasian kanssa, että ryhmä on syklinen kohdassa , ja , se on ristiriidassa sen kanssa, että ryhmällä on eksponentti . ■ $q$ $a$ $a^{\lambda (n)/q}\equiv 1{\pmod {n))$ $\lambda (n)=\operaattorinimi {lcm} [\lambda (p_{1}^{a_{1))),\;\lambda (p_{2}^{a_{2))),\ pisteet ,\lambda (p_{s}^{a_{s}})].$ $q$ $\lambda (p_{i}^{a_{i)))$ $a$ $a^{\lambda (p_{i}^{a_{i)))/q}\equiv 1{\pmod {p_{i}^{a_{i))))$ $\mathbb {Z} _{p^{k}}^{\times }$ $p>2$ $p = 2$ $\mathbb {Z} _{2^{k}}^{\times }$ $2^{k-2}$

Yhteys Carmichaelin, Eulerin ja Fermatin lauseiden välillä

Koska Carmichael-funktio jakaa Eulerin funktion (osamääräsarja, katso OEIS- sekvenssi A034380 ), Carmichaelin lause on vahvempi tulos kuin klassinen Eulerin lause . On selvää, että Carmichaelin lause liittyy Eulerin lauseeseen , koska äärellisen Abelin ryhmän eksponentti jakaa aina ryhmän järjestyksen. Carmichael- ja Euler-funktiot eroavat toisistaan pienilläkin argumenteilla: , mutta ne eroavat aina, kun modulojäännösryhmässä ei ole generaattoria (katso sekvenssi A033949 ). $\lambda (n)$ $\varphi (n)$ $\lambda (15)=4$ $\varphi (15)=8$ $n$

Fermat'n pieni lause on Eulerin lauseen erikoistapaus, jossa moduuli on alkuluku. Carmichaelin lause alkumoduuleille antaa saman väitteen, koska jäännösryhmä modulo alkuluku on syklinen , eli sen järjestys ja eksponentti ovat samat. $n$

Carmichael-funktion ominaisuudet

Jaettavuus

a|b\Rightarrow \lambda (a)|\lambda (b)

Carmichael-funktio NOC:sta

Kaikille luonnollisille lukuille se on totta $a,b$

\lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))

Tämä seuraa välittömästi Carmichaelin funktion määritelmästä.

Alkukantaiset yhtenäisyyden juuret

Jos ja ovat koprime ja ovat modulo- eksponentteja , sitten $a,n$ $m$ $a$ $n$

m|\lambda (n)

Toisin sanoen jäännösrenkaan modulo -yksikön primitiivisen yksikköjuuren järjestys jakaa . Ryhmäteorian puitteissa tämä väite on yksinkertainen seuraus ryhmän eksponentin määritelmästä. $n$ $\lambda (n)$

Eksponenttisyklin pituus

Jos for tarkoittaa suurinta alkulukujen indeksiä kanonisessa hajotuksessa , niin kaikille (mukaan lukien ei koprime kanssa ) ja kaikille , $n$ ${\displaystyle x_{\max ))$ $n$ $a$ $n$ ${\displaystyle k\geqslant x_{\max ))$

a^{k}\equiv a^{k+\lambda (n)}{\pmod {n))

Erityisesti neliöttömälle (sille ), kaikille $n$ $n$ $x_{\max }=1$ $a$

a\equiv a^{\lambda (n)+1}{\pmod {n))

Keskimääräiset ja tyypilliset arvot

Kaikille ja jatkuvasti : $x>16$ $B$

{\displaystyle {\frac {1}{x}}\sum \limits _{n\leq x}\lambda (n)={\frac {x}{\ln x}}e^{B(1+o (1))\ln \ln x/(\ln \ln \ln x)))

[1] [2] .

Tässä

B=e^{-\gamma }\prod _{p}\left({1-{\frac {1}{(p-1)^{2}(p+1)))}\oikea )\noin 0,34537\ .

Kaikille ja kaikille paitsi numeroille on totta, että: $N$ $n\leqslant N$ $o(N)$

{\displaystyle \lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)))

missä on vakio [2] [3] , $A$

A=-1+\sum \limits _{p}{\frac {\ln p}{(p-1)^{2}}}\noin 0,2269688\ .

Alarajat

Tarpeeksi suurille ja mille tahansa , on olemassa ainakin $N$ $\Delta \geq \ln ^{3}\ln N$

{\displaystyle Ne^{-0.69{\sqrt[{3}]{\Delta \ln \Delta ))))

luonnolliset luvut siten, että [4] . $n\leq N$ ${\displaystyle \lambda (n)\leqslant ne^{-\Delta ))$

Kaikille luonnollisten lukujen sarjalle , mille tahansa vakiolle ja riittävän suurelle : $n_{1}<n_{2}<n_{3}<\cdots$ $0<c<1/\ln 2$ $i$

\lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i))

[5] [6] .

Pienet arvot

Vakiolle ja riittävän suurelle positiiviselle on olemassa sellainen kokonaisluku , että [6] . Lisäksi tämä näyttää $c$ $A$ $n>A$ $\lambda (n)<(\ln A)^{c\ln \ln \ln A}$ $n$

n=\prod \limits _{(q-1)|m,\ q{\text{ on alkuluku))}q

joillekin ruuduista vapaa [5] . $m<(\ln A)^{c\ln \ln \ln A}$

Carmichael-funktion arvojoukko

Carmichael-funktion arvojoukolla, joka ei ylitä , on kardinaalisuus $x$

{\frac {x}{\ln ^{\eta +o(1)}x}}\ ,

missä [7] $\eta =1-(1+\ln \ln 2)/\ln 2=0.08607\dots$

Katso myös

Muistiinpanot

↑ Lause 3 teoksessa Erdos (1991)
↑ 1 2 Sandor & Crstici (2004) s. 194
↑ Lause 2 teoksessa Erdos (1991)
↑ Lause 5 julkaisussa Friedlander (2001)
↑ 1 2 Lause 1 Erdosissa 1991
↑ 1 2 Sandor & Crstici (2004) s. 193
↑ Ford, Kevin; Luca, Florian & Pomerance, Carl (27. elokuuta 2014), Carmichaelin ?-funktion kuva, arΧiv : 1408.6506 [math.NT].

Kirjallisuus

Bukhshtab A.A. Numeroteoria. - M .: Koulutus, 1966. (luku 11, s. 2)
Erdos, Paul; Pomerance, Carl; Schmutz, Eric. Carmichaelin lambda-funktio (neopr.) // Acta Arithmetica. - 1991. - T. 58 . - S. 363-385 . — ISSN 0065-1036 .
Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. Tehogeneraattorin jakso ja Carmichael-funktion pienet arvot // Laskennan matematiikka : päiväkirja. - 2001. - Voi. 70 . - P. 1591-1605, 1803-1806 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-00-01282-5 .
Sandor, Jozsef; Crstici, Borislav. Lukuteorian käsikirja II (uuspr.) . - Dordrecht: Kluwer Academic , 2004. - S. 32-36,193-195. — ISBN 1-4020-2546-7 .
Carmichael, R. D. Numeroteoria (määrittelemätön) . - Nabu Press. — ISBN 1144400341 .