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(\mathrm{mod}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 Sablon:OEIS a $\phi$ 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
$\phi (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{array}{cc}\phi (n)& \text{ha }n=2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,\dots \\ \frac{1}{2}\phi (n)& \text{ha }n=8,16,32,64,128,256,\dots \end{array}$

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

$\phi (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(\mathrm{mod}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(\mathrm{mod}n)$.

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

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

$a^{p^k(p-1)}=(1+h{p}^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(\mathrm{mod}{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(\mathrm{mod}{2}^k)$.

Az eredmények hierarchiája

Mivel λ(n) osztója φ(n)-nek (a hányadosok itt találhatók: Sablon:Oeis), 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 Sablon:OEIS2C 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(\mathrm{mod}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\ge x_{max}$-ra igaz, hogy:

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

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

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

Átlagos és tipikus értéke

Bármely x > 16-ra:

$\frac{1}{x}\sum _{n\le 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 $\mathrm{\Delta }\ge (\ln \ln N{)}^3$-ra legfeljebb

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

$n\le N$ pozitív egész létezik, melyre $\lambda (n)\le n{e}^{-\mathrm{\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

• Sablon:Fordítás

Kapcsolódó szócikkek

• Carmichael-számok

Források

• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite book