Carmichael-függvény

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

${\displaystyle 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 ${\displaystyle \psi (n)}$.

A ${\displaystyle \lambda (n)}$ Carmichael-függvény első 36 eleme (A002322 sorozat az OEIS-ben) a ${\displaystyle \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
${\displaystyle \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
${\displaystyle \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.^[1]

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:

${\displaystyle \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:

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

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

${\displaystyle 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):

${\displaystyle \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

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

ahol ${\displaystyle \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 ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$.

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

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

${\displaystyle 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 ${\displaystyle a^{p^{k-1}(p-1)}\equiv 1{\pmod {p^{k}}}}$.

${\displaystyle a=1+2h}$

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

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

${\displaystyle 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 ${\displaystyle 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

${\displaystyle a|b\Rightarrow \lambda (a)|\lambda (b)}$

Kompozíció

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

${\displaystyle \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 ${\displaystyle a}$ és ${\displaystyle n}$ relatív prímek és ${\displaystyle m}$ a legkisebb kitevő, amire ${\displaystyle a^{m}\equiv 1{\pmod {n}}}$, akkor

${\displaystyle m|\lambda (n)}$ .

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

Exponenciális ciklushosszúság

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

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

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

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

Átlagos és tipikus értéke

Bármely x > 16-ra:

${\displaystyle {\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)}}$.^[2][3]

ahol B konstans:

${\displaystyle 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:

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

ahol A konstans,^[3][4]

${\displaystyle 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 ${\displaystyle \Delta \geq (\ln \ln N)^{3}}$-ra legfeljebb

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

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

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

${\displaystyle \lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i}}}$.^[6][7]

Kis értékei

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

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

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

Értékkészlet

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

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

ahol ${\displaystyle \eta =1-{\frac {1+\log \log 2}{\log 2}}=0,08607}$….^[8]

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

Jegyzetek

1. Archivált másolat. [2011. június 15-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. január 5.)
2. Theorem 3 in Erdős (1991)
3. Sándor & Crstici (2004) p.194
4. Theorem 2 in Erdős (1991)
5. Theorem 5 in Friedlander (2001)
6. Theorem 1 in Erdős 1991
7. Sándor & Crstici (2004) p.193
8. Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function"

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