Carmichael függvény

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 1-jén felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Carmichael-függvény egy számelméleti függvény , amelyet jelöl , és egyenlő a legkisebb kitevővel , $\lambda (n)$ $m$

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

minden egész számra coprime modulo -val . A csoportelmélet nyelvén a modulo multiplikatív maradékcsoport kitevője . $a$ $n$ $\lambda (n)$ $n$

Itt van egy táblázat az A002322 függvénysorozat első 36 értékéről az OEIS - ben , összehasonlítva az Euler-függvény értékeivel . (a különböző értékek félkövérrel vannak kiemelve) $\lambda (n)$ $\varphi$

n	egy	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy	tizenöt	16	17	tizennyolc	19	húsz	21	22	23	24	25	26	27	28	29	harminc	31	32	33	34	35	36
$\lambda (n)$	egy	egy	2	2	négy	2	6	2	6	négy	tíz	2	12	6	négy	négy	16	6	tizennyolc	négy	6	tíz	22	2	húsz	12	tizennyolc	6	28	négy	harminc	nyolc	tíz	16	12	6
$\varphi (n)$	egy	egy	2	2	négy	2	6	négy	6	négy	tíz	négy	12	6	nyolc	nyolc	16	6	tizennyolc	nyolc	12	tíz	22	nyolc	húsz	12	tizennyolc	12	28	nyolc	harminc	16	húsz	16	24	12

Példa

Az 1,3,5,7 mind 8-nál kisebb szám, és viszonylag prím ehhez képest, így a Carmichael-függvény 2. Az Euler-függvény 4, mivel pontosan 4 szám van az 1,3,5,7 listában. $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)$

Carmichael tétele

A páratlan prímek hatványainak Carmichael-függvénye , valamint a 2-es és 4-es számok esetében megegyezik az Euler-függvénnyel ; 4-nél nagyobb kettő hatványa esetén egyenlő az Euler-függvény felével: $\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\pontok \\{\frac {1}{2}}\varphi (n)&{\text{if }} n=8,16,32,64,128,256\pontok \end{esetek}}

A prímek hatványainak Euler-függvénye az

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

Az aritmetika alaptétele szerint bármelyiket úgy ábrázolhatjuk $n>1$

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

hol vannak a prímszámok és minden . ${\displaystyle p_{1}<p_{2}<\dots <p_{s))$ $a_{i}>0$

Általános esetben a faktorizációban szereplő prímszámok pontos hatványainak legkisebb közös többszöröse : $\lambda (n)$ $\lambda (p_{i}^{a_{i)))$ $n$

\lambda (n)=\operátornév {lcm} [\lambda (p_{1}^{a_{1))),\;\lambda (p_{2}^{a_{2))),\ pontok ,\lambda (p_{s}^{a_{s}})].

Carmichael tétele

Ha koprime, akkor $a,n$

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

Más szóval, a Carmichael-tétel kimondja, hogy a fenti képlettel definiált függvény valójában megfelel a Carmichael-függvény definíciójának. Ez a tétel primitív gyökök és a kínai maradéktétel segítségével igazolható .

Bizonyíték

Először bizonyítsuk be, hogy minden c koprímre , . $a$ $n$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Fermat kis tétele szerint minden egyszerű modulhoz és a modul bármely másodszámához megkapjuk a . $p$ $a$ $a^{p-1}=1+hp$

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

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

Ekkor a matematikai indukció módszerével azt kapjuk, hogy minden . $a$ ${\displaystyle a^{p^{k-1}(p-1)}=a^{\lambda (p^{k})}\equiv 1{\pmod {p^{k))))$

A 2. modul esetében az összefüggés valamivel erősebb:

Ha furcsa, akkor . $a$ $a=1+2h$

Akkor . ${\displaystyle a^{2}=1+4ó(ó+1)=1+8C_{ó+1}^{2))$

Következő, ha , akkor $a^{2^{k-2}}=1+2^{k}h$

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

Ekkor matematikai indukcióval azt kapjuk, hogy minden páratlan esetén igaz, hogy . $a$ $k\geqslant 3$ ${\displaystyle a^{2^{k-2}}=a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k))))$

Végül, ha és a koprím -val , akkor és , így és és akkor . $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))$

Vegye figyelembe azt is, hogy az állítást nem lehet megerősíteni: a kitevő az a minimum, amelyre . Ez ellentmondásokkal könnyen igazolható. $a$ $\lambda (n)$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Valóban, legyen olyan prímszám , hogy mindenki számára . Mivel , majd oszt néhány , azaz minden . Ez azonban ellentmond annak a ténynek, hogy a csoport ciklikus a , és -nél , ez ellentmond annak, hogy a csoportnak van kitevője . ■ $q$ $a$ $a^{\lambda (n)/q}\equiv 1{\pmod {n))$ $\lambda (n)=\operátornév {lcm} [\lambda (p_{1}^{a_{1))),\;\lambda (p_{2}^{a_{2))),\ pontok ,\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}$

Kapcsolat Carmichael, Euler és Fermat tételei között

Mivel a Carmichael-függvény osztja az Euler-függvényt (a hányadosok sorozatát lásd az OEIS sorozatban A034380 ), a Carmichael-tétel erősebb eredmény, mint a klasszikus Euler-tétel . Nyilvánvaló, hogy a Carmichael-tétel összefügg az Euler-tétellel , mert egy véges Abel-csoport kitevője mindig felosztja a csoport sorrendjét. A Carmichael és az Euler függvények még kis argumentumok esetén is különböznek: , de mindig különböznek, ha a modulo maradékcsoportnak nincs generátora (lásd az A033949 sorozatot ). $\lambda (n)$ $\varphi (n)$ $\lambda (15)=4$ $\varphi (15)=8$ $n$

A Fermat-féle kis tétel az Euler-tétel speciális esete, amelyben a modulus egy prímszám. A prímmodulokra vonatkozó Carmichael-tétel ugyanezt az állítást adja, mivel a modulo prím maradékcsoport ciklikus , azaz sorrendje és kitevője megegyezik. $n$

A Carmichael függvény tulajdonságai

Oszthatóság

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

A Carmichael függvény a NOC-ból

Minden természetes számra igaz, hogy $a,b$

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

Ez rögtön következik a Carmichael-függvény meghatározásából.

Az egység primitív gyökerei

Ha és a koprím és modulo kitevők , akkor $a,n$ $m$ $a$ $n$

m|\lambda (n)

Más szóval, a maradék gyűrű primitív egységgyökének sorrendje modulo osztódik . A csoportelmélet keretében ez az állítás a csoport kitevőjének meghatározásának egyszerű következménye. $n$ $\lambda (n)$

Kitevő ciklus hossza

Ha for jelöli a prímszámok legnagyobb indexét a kanonikus dekompozícióban , akkor az összesre (beleértve a -val együtt prímet ) és az összesre , $n$ ${\displaystyle x_{\max ))$ $n$ $a$ $n$ ${\displaystyle k\geqslant x_{\max ))$

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

Különösen egy négyzet nélküli (azért ), mindenkinek $n$ $n$ $x_{\max }=1$ $a$

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

Átlagos és tipikus értékek

Bármilyen és állandóra : $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] .

Itt

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

Bármelyikre , kivéve a számokat, igaz, hogy: $N$ $n\leqslant N$ $o(N)$

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

ahol egy állandó [2] [3] , $A$

A=-1+\sum \limits _{p}{\frac {\ln p}{(p-1)^{2}}}\körülbelül 0,2269688\ .

Alsó határok

Elég nagy és bármilyen , létezik legalább $N$ $\Delta \geq \ln ^{3}\ln N$

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

természetes számok úgy, hogy [4] . $n\leq N$ ${\displaystyle \lambda (n)\leqslant ne^{-\Delta ))$

Természetes számok bármely sorozatára , bármely állandóra és elég nagyra : $n_{1}<n_{2}<n_{3}<\cdots$ $0<c<1/\ln 2$ $én$

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

[5] [6] .

Kis értékek

Egy állandó és kellően nagy pozitívhoz létezik olyan egész szám , amelyre [6] . Ráadásul ez úgy néz ki $c$ $A$ $n>A$ $\lambda (n)<(\ln A)^{c\ln \ln \ln A}$ $n$

n=\prod \limits _{(q-1)|m,\ q{\text{ a prím))}q

egyeseknél négyzetektől mentes [5] . $m<(\ln A)^{c\ln \ln \ln A}$

A Carmichael-függvény értékkészlete

A Carmichael-függvény értékeit meg nem haladó értékkészlete kardinalitású $x$

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

ahol [7] $\eta =1-(1+\ln \ln 2)/\ln 2=0,08607\pontok$

Lásd még

Jegyzetek

↑ Erdos (1991) 3. tétele
↑ 1 2 Sándor és Crstici (2004) 194. o
↑ Erdos 2. tétele (1991)
↑ Friedlander 5. tétele (2001)
↑ 1 2 1. tétel Erdos 1991-ben
↑ 1 2 Sándor és Crstici (2004) 193. o
↑ Ford, Kevin; Luca, Florian és Pomerance, Carl (2014. augusztus 27.), Carmichael ?-függvényének képe, arΧiv : 1408.6506 [math.NT].

Irodalom

Bukhshtab A. A. Számelmélet. - M .: Oktatás, 1966. (11. fej. 2. o.)
Erdos, Paul; Pomerance, Carl; Schmutz, Eric. Carmichael lambda függvénye (neopr.) // Acta Arithmetica. - 1991. - T. 58 . - S. 363-385 . — ISSN 0065-1036 .
Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. Az áramfejlesztő periódusa és a Carmichael-függvény kis értékei // Számítási matematika : folyóirat. - 2001. - 20. évf. 70 . - P. 1591-1605, 1803-1806 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-00-01282-5 .
Sándor József; Crstici, Borislav. Számelmélet kézikönyve II (neopr.) . - Dordrecht: Kluwer Academic , 2004. - S. 32-36,193-195. — ISBN 1-4020-2546-7 .
Carmichael, R. D. A számelmélet (meghatározatlan) . — Nabu Press. — ISBN 1144400341 .