Ugrás a tartalomhoz

Carmichael-függvény

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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élda

[szerkeszté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étel

[szerkeszté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ás

[szerkeszté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

[szerkeszté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 OEISA033949 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

[szerkesztés]

Oszthatóság

[szerkeszté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ök

[szerkeszté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ág

[szerkeszté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éke

[szerkeszté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átok

[szerkeszté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ékei

[szerkeszté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észlet

[szerkesztés]

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

ahol ….[8]

Fordítás

[szerkeszté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

[szerkesztés]

Jegyzetek

[szerkeszté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"

Források

[szerkesztés]