Carmichael-függvény
A matematika, azon belül a számelmélet területén a pozitív egész n-eken értelmezett, -nel jelölt Carmichael-függvény értéke az a legkisebb m pozitív egész szám, melyre
, 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 .

A  Carmichael-függvény első 36 eleme  a  Euler-függvényhez hasonlítva (félkövér, ha különbözőek):

Numerikus példa
72 = 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 74 = 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:

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

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

alakban, ahol p1 < p2 < ... < pω prímszámok és ai > 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):

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

ahol  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 kis Fermat-tétel alapján .

Teljes indukcióval .

Teljes indukcióval, ha k ≥ 3, akkor .

Az eredmények hierarchiája

Mivel λ(n) osztója φ(n)-nek (a hányadosok itt találhatók: ), 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  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

Kompozíció

Minden  és  pozitív egész számra fennáll, hogy
 .

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  és  relatív prímek és
 a legkisebb kitevő, amire ,
akkor
 .
Tehát a modulo  egészek gyűrűje primitív egységgyökeinek a rendjei osztói a -nek.

Exponenciális ciklushosszúság
Vegyünk egy  számot, mely prímfelbontásában szereplő maximális kitevő . Ekkor minden -ra (az -nel nem relatív prímekre is) és minden -ra igaz, hogy:

.

Ha pedig  négyzetmentes (), akkor minden  -ra igaz, hogy:

.

Átlagos és tipikus értéke

Bármely x > 16-ra:

.

ahol B konstans:

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

ahol A konstans,Theorem 2 in Erdős (1991)

Alsó korlátok

Bármely elegendően nagy N-re és bármely -ra legfeljebb

 pozitív egész létezik, melyre .

Bármely pozitív egészekből álló  sorozatra,  konstansra és elegendően nagy i-re igaz, hogy:
.Sándor & Crstici (2004) p.193

Kis értékei
Bármely c konstanshoz és elegendően nagy pozitív A számhoz, létezik olyan  egész szám, melyre .
Továbbá, n'' felírható

alakban valamely négyzetmentes  egészre.

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

ahol ….

Fordítás

Kapcsolódó szócikkek
 Carmichael-számok

Jegyzetek

Források
 
 
 
 

Számelmélet