Euler-függvény
A Wikipédiából, a szabad lexikonból.
A
-nel jelölt Euler-függvény (vagy Euler-féle fí-függvény) a matematikában a számelmélet, különösen a moduláris számelmélet egyik igen fontos függvénye, egy egész számokon értelmezett egész értékű ún. számelméleti függvény.
Legelemibb meghatározása, hogy egy adott egész számhoz a nála kisebb relatív prím pozitív egész számok számát adja meg.
Formálisan:
.Egy másik, de fentivel teljességgel azonos függvényt adó értelmezésben e függvény az n-hez redukált maradékosztályok számát adja meg (ez gyakorlatilag ugyanaz, mint az előbbi definíció, elvontaban, a maradékaritmetika kifejezéseivel megfogalmazva).
Félig-meddig explicit (a számelmélet alaptételét használó) képlet is adható e függvény kiszámítására, ld. lentebb.
Tartalomjegyzék |
[szerkesztés] Értékei kis számokra
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|
[szerkesztés] Legfontosabb tulajdonságai
[szerkesztés] Multiplikativitás
Talán a legfontosabb tulajdonsága, hogy („gyengén”) multiplikatív, azaz relatív prím számok szorzatán ugyanazt az értéket veszi fel, mint ami a két számon felvett értékének szorzata:

Például:
- a=7 az prím szám, és

- b=11 szintén prím, és

(lásd az Értékei kis számokra c. táblázatot)
A két prímszám szorzata:
, valamint
, ami pontosan
.
[szerkesztés] Kiszámítása
- Viszonylag könnyű belátni a következőket:
- Ha n = p prímszám, akkor
(mert éppen akkor prím egy p egész szám, ha minden nála kisebb pozitív szám relatív prím hozzá, különben lenne önmagánál kisebb prímosztója!) . - Ha
prímhatvány, akkor 
- Ha n = p prímszám, akkor
- Általánosabb n-re a multiplikativitás és az előző kis tulajdonság alapján, a számelmélet alaptétele felhasználásával számítható ki;
- Bár talán még elemibb módszer, ha csak a szitaformulát használjuk. Ekkor az így kapott képletből is adódik a multiplikativitás (mindkét módszer persze ugyanazt a képletet eredményezi): ha
,
, és pi (páronként) különböző prímek, akkor érvényes

, feltéve hogy 
ahol tehát m az n szám különböző prímtényezőinek száma, pi pedig valamely prímtényezője. A képlet n=0,1-re nem alkalmazható, de mind az elemi, mind a formális definíció szerint φ(0)=0, φ(1)=1.
Például φ(10) = 10×(1-1/2)×(1-1/5) = 10×(1/2)×(4/5)=4; és valóban az 1,2,3,4,5,6,7,8,9,10 számok közt négy darab 10-hez relatív prím van: 1, 3, 7, és 9.
A Möbius-függvény segítségével ez

alakban írható.
[szerkesztés] Az osztókra összeadva

Ez bizonyítható az explicit formulából, de így is: vegyük az

törteket. Ezek száma nyilván n. Írjuk mindegyiket egyszerűsített formában! Ekkor ezek a/d alakú törtek lesznek, ahol d osztója n-nek. Adott d-hez azok az a számlálók adódnak, amelyekkel egyszerűsített törtet alkot, azaz, ha (a,d)=1. Innen adódik a kívánt azonosság.
[szerkesztés] Összegfüggvénye

[szerkesztés] Egyéb
- Külföldön néha Euler's totient functionnak, azaz kb. „Euler annyiszoros-függvényének” nevezik, itt a totient szó a latin eredetű totiens (annyiszor(os), ahány) szóból származik, állítólag a quotiens („hányszoros”, azaz hányados, kvóciens) mintájára alkotta meg J. J. Sylvester 1879-ben: "The so-called φ function of any number I shall here and hereafter designate as its τ function and call its Totient." .
- Máig megoldatlan a következő probléma, a Carmichael-sejtés: „Az Euler-függvény minden értéket legalább két helyen vesz fel.”
- Néha a Gamma-függvényt is nevezik Euler-féle gammafüggvénynek.


Based on work by