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 (A002322 sorozat az OEIS-ben) a 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
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
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éldaSzerkesztés

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.[1]

Carmichael-tételSzerkesztés

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ásSzerkeszté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ájaSzerkesztés

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ágaiSzerkesztés

OszthatóságSzerkesztés

 

KompozícióSzerkesztés

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ökSzerkesztés

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ágSzerkesztés

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ékeSzerkesztés

Bármely x > 16-ra:

 .[2][3]

ahol B konstans:

 

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

 

ahol A konstans,[3][4]

 

Alsó korlátokSzerkesztés

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

 

  pozitív egész létezik, melyre  .[5]

Bármely pozitív egészekből álló   sorozatra,   konstansra és elegendően nagy i-re igaz, hogy:

 .[6][7]

Kis értékeiSzerkesztés

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

 

alakban valamely négyzetmentes   egészre.[6]

ÉrtékkészletSzerkesztés

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

 

ahol  ….[8]

FordításSzerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Kapcsolódó szócikkekSzerkesztés

JegyzetekSzerkesztés

  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. a b Sándor & Crstici (2004) p.194
  4. Theorem 2 in Erdős (1991)
  5. Theorem 5 in Friedlander (2001)
  6. a b Theorem 1 in Erdős 1991
  7. a b Sándor & Crstici (2004) p.193
  8. Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function"