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
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< 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őeleme a Euler-függvényhez hasonlítva ( félkövér , ha különbözőek ) : Numerikus példa 72 =≡( mod mivel aés arelatív prímek ( legnagyobb közös osztójuk nincsenek közös prímtényezőik ) és a Carmichael-függvény értékenál Az Euler-függvény értékenál mivelolyan szám van , aminál kisebb éscal relatív prím és Bár az Euler–Fermat-tétel miatt természetesen igaz , hogy=≡( mod szükségtelenet a negyedik hatványra emelni , mivel a Carmichael-függvény megmutatja , hogya négyzeten kongruensgyel ( mod Akettőnél nagyobb hatványokra emelése csak a ciklust ismétli . Ugyanez áll fent aés azesetében , így látható hogy a Carmichael-szám ittés nem Carmichael-tétel Páratlan prímszámok hatványai és ezek kétszeresei esetében , valamint aésesetében a λ ( n ) értéke éppen megegyezik φ( n)-nel , az Euler-függvény értékével ; anél nagyobbhatvá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 >egyértelműen felírható alakban , ahol p1 < p2 <\... < pω prímszámok és ai > ( az n =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 ≥ 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 ) = míge φ( 15 ) =( 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 − 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 >ra : . ahol B konstans : Minden N számra és legfeljebb o ( N ) n ≤ N pozitív egészre : ahol A konstans,Theoremin Erdős 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 & Crsticip.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