Carmichael-függvény

A matematika, azon belül a számelmélet területén a pozitív egész n-eken értelmezett, $\lambda (n)$-nel jelölt Carmichael-függvény értéke az a legkisebb m pozitív egész szám, melyre

$a^{m}\equiv 1{\pmod {n}}$, ha a és n relatív prímek és 1 < a < n .

Minden n-hez relatív prím a egész számra. Az algebrai eszközeivel kifejezve, a modulo n egész számok multiplikatív csoportjának az exponensét határozza meg. A Carmichael-függvény ismert még mint a redukált tóciens függvény vagy a legkisebb univerzális exponens-függvény, jelölése itt néha $\psi (n)$.

A $\lambda (n)$ Carmichael-függvény első 36 eleme (A002322 sorozat az OEIS-ben) a $\varphi$ Euler-függvényhez hasonlítva (félkövér, ha különbözőek):

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
$\lambda (n)$	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2	20	12	18	6	28	4	30	8	10	16	12	6
$\varphi (n)$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12

Numerikus példa

7² = 49 ≡ 1 (mod 8), mivel a 7 és a 8 relatív prímek (legnagyobb közös osztójuk 1; nincsenek közös prímtényezőik) és a Carmichael-függvény értéke 8-nál 2. Az Euler-függvény értéke 8-nál 4, mivel 4 olyan szám van, ami 8-nál kisebb és 8-cal relatív prím (1, 3, 5, és 7). Bár az Euler–Fermat-tétel miatt természetesen igaz, hogy 7⁴ = 2401 ≡ 1 (mod 8), szükségtelen 7-et a negyedik hatványra emelni, mivel a Carmichael-függvény megmutatja, hogy 7 a négyzeten kongruens 1-gyel (mod 8). A 7 kettőnél nagyobb hatványokra emelése csak a 7, 1, 7, 1… ciklust ismétli. Ugyanez áll fent a 3 és az 5 esetében, így látható hogy a Carmichael-szám itt 2 és nem 4.

Carmichael-tétel

Páratlan prímszámok hatványai és ezek kétszeresei esetében, valamint a 2 és 4 esetében a λ(n) értéke éppen megegyezik φ(n)-nel, az Euler-függvény értékével; a 4-nél nagyobb 2-hatványok esetében pedig az Euler-függvény értékének felével:

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

A prímhatványokra vonatkozó egyenlőség az Euler-függvénnyel abból adódik, hogy:

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

A számelmélet alaptétele szerint bármely n > 1 egyértelműen felírható

$n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}}$

alakban, ahol p₁ < p₂ < ... < p_ω prímszámok és a_i > 0. (az n = 1 az üres szorzatnak felel meg.)

Általános n-re, λ(n) megegyezik az összes prímhatvány-tényező λ értékeinek legkisebb közös többszörösével (lkkt):

$\lambda (n)={\text{lkkt}}[\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].$

A Carmichael-tétel kimondja, hogy ha a és n relatív prímek, akkor

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

ahol $\lambda$ a fentebb meghatározott Carmichael-függvény. Másszóval, kimondja a fenti képletek helyességét. Ez bebizonyítható bármely primitív gyök és a kínai maradéktétel figyelembe vételével.

Bizonyítás

Hogyha a és n relatív prímek, fennáll, hogy $a^{\lambda (n)}\equiv 1{\pmod {n}}$.

A kis Fermat-tétel alapján $a^{p-1}=1+hp$.

$a^{p^{k-1}(p-1)}=1+hp^{k}$

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

Teljes indukcióval $a^{p^{k-1}(p-1)}\equiv 1{\pmod {p^{k}}}$.

$a=1+2h$

$a^{2}=1+4h(h+1)=1+8C_{h+1}^{2}$

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

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

Teljes indukcióval, ha k ≥ 3, akkor $a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}$.

Az eredmények hierarchiája

Mivel λ(n) osztója φ(n)-nek (a hányadosok itt találhatók: (A034380 sorozat az OEIS-ben)), a Carmichael-tétel erősebb eredmény a korábbi Euler–Fermat-tételnél. Nyilvánvaló, hogy a két tétel összekapcsolódik, hiszen egy véges Abel-csoport kitevőjének osztania kell a csoport rendjét, elemi csoportelméleti megfontolásokból. A két függvény értékei már egész kis esetekre is eltérnek egymástól: λ(15) = 4, míge φ(15) = 8 (lásd  A033949 a megfelelő n-ekhez).

A kis Fermat-tétel az Euler–Fermat-tétel speciális esete, ahol n egy p prímszámmal egyezik meg. A Carmichael-tétel p prímszámra ugyanazt az eredményt adja, mivel a kérdéses csoport ilyenkor ciklikus csoport, melynek rendje és kitevője egyaránt p − 1.

A Carmichael-függvény tulajdonságai

Oszthatóság

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

Kompozíció

Minden $a$ és $b$ pozitív egész számra fennáll, hogy

$\lambda ({\text{lkkt}}(a,b))={\text{lkkt}}(\lambda (a),\lambda (b))$ .

Ez a Carmichael-függvény rekurzív definíciójának a következménye.

Primitív m-edik egységgyökök

Ha $a$ és $n$ relatív prímek és $m$ a legkisebb kitevő, amire $a^{m}\equiv 1{\pmod {n}}$, akkor

$m|\lambda (n)$ .

Tehát a modulo $n$ egészek gyűrűje primitív egységgyökeinek a rendjei osztói a $\lambda (n)$-nek.

Exponenciális ciklushosszúság

Vegyünk egy $n$ számot, mely prímfelbontásában szereplő maximális kitevő $x_{max}$. Ekkor minden $a$-ra (az $n$-nel nem relatív prímekre is) és minden $k\geq x_{max}$-ra igaz, hogy:

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

Ha pedig $n$ négyzetmentes ($x_{max}=1$), akkor minden $a$-ra igaz, hogy:

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

Átlagos és tipikus értéke

Bármely x > 16-ra:

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

ahol B konstans:

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

Minden N számra és legfeljebb o(N) n ≤ N pozitív egészre:

$\lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)}\,$

ahol A konstans,

$A=-1+\sum _{p}{\frac {\log p}{(p-1)^{2}}}\approx 0,2269688\ .$

Alsó korlátok

Bármely elegendően nagy N-re és bármely $\Delta \geq (\ln \ln N)^{3}$-ra legfeljebb

$Ne^{-0,69(\Delta \ln \Delta )^{1/3}}$

$n\leq N$ pozitív egész létezik, melyre $\lambda (n)\leq ne^{-\Delta }$.

Bármely pozitív egészekből álló $n_{1}<n_{2}<n_{3}<\cdots$ sorozatra, $0<c<1/\ln 2$ konstansra és elegendően nagy i-re igaz, hogy:

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

Kis értékei

Bármely c konstanshoz és elegendően nagy pozitív A számhoz, létezik olyan $n>A$ egész szám, melyre $\lambda (n)<(\ln A)^{c\ln \ln \ln A}$. Továbbá, n felírható

$n=\prod _{(q-1)|m{\text{ és }}q{\text{ prímszám}}}q$

alakban valamely négyzetmentes $m<(\ln A)^{c\ln \ln \ln A}$ egészre.

Értékkészlet

A Carmichael-függvény értékkészletének számláló függvénye

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

ahol $\eta =1-{\frac {1+\log \log 2}{\log 2}}=0,08607$….

Fordítás

• Ez a szócikk részben vagy egészben a Carmichael function című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Kapcsolódó szócikkek

• Carmichael-számok

Források

• (1991) „Carmichael's lambda function”. Acta Arithmetica 58, 363–385. o. ISSN 0065-1036. 
• (2001) „Period of the power generator and small values of the Carmichael function”. Mathematics of Computation 70, 1591–1605, 1803–1806. o. DOI:10.1090/s0025-5718-00-01282-5. ISSN 0025-5718. 
• Handbook of number theory II. Dordrecht: Kluwer Academic, 32–36,193–195. o. (2004). ISBN 1-4020-2546-7 
• Carmichael, R. D.. The Theory of Numbers. ISBN 1144400341