Euler-függvény

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. J. J. Sylvester 1879-ben a totient (kb. „annyiszoros”, magyarul a hányados-kvóciens mintájára esetleg tóciens) függvény nevet adta neki.

Legelemibb meghatározása, hogy egy adott pozitív egész számhoz a nála nem nagyobb 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 a modulo n redukált maradékosztályok számát adja meg (ez gyakorlatilag ugyanaz, mint az előbbi definíció, elvontabban, 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.

Általánosítása a Jordan-függvény.

Értékei kis számokra

Legfontosabb tulajdonságai

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 .

Kiszámítása 

 Viszonylag könnyű belátni a következőket:
 Ha  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 

 Á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  (páronként) különböző prímek, akkor érvényes
    , feltéve, hogy  
ahol tehát  az  szám különböző prímtényezőinek száma,  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ó.

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 . Innen adódik a kívánt azonosság.

Összegfüggvénye

Tóciens számok
Egy totient vagy tóciens szám (a kvóciens mintájára) az Euler-függvény által felvett érték, tehát a φ függvény értékkészletének egy eleme. Olyan m egész, amihez létezik legalább egy olyan n, amire φ(n) = m. A tóciens m szám valenciáján vagy multiplicitásán az előbbi egyenlet megoldásainak számát értjük (tehát hogy a φ függvény hányszor veszi fel az m értéket). Egy nontóciens szám alatt olyan természetes számot értünk, ami nem tóciens szám; az egynél nagyobb páratlan számok mind ilyenek, de rajtuk kívül is végtelen sok nontóciens szám létezik, és minden páratlan számnak létezik páros, nontóciens többszöröse.

Az x-nél kisebb tóciens számok határértéke
,
ahol a konstans C = 0,8178146... .

Ha a multiplicitást figyelembe véve számoljuk össze, az x-nél kisebb tóciens számokat megadó képlet:
,
ahol az R hibatag nagyságrendje legfeljebb  bármilyen pozitív k-ra.

Ismert az is, hogy m multiplicitása végtelen sokszor haladja meg mδ-t, amennyiben δ < 0,55655.

Ford tétele
 igazolta, hogy minden k ≥ 2 egész számhoz létezik k multiplicitású m tóciens szám; tehát amire a φ(n) = m egyenletnek pontosan k megoldása van; az eredményt korábban Wacław Sierpiński sejtette meg, Schinzel H hipotézise folyományaként. Valóban, minden előforduló multiplicitás végtelen sokszor is előfordul.

Nem ismerünk azonban olyan m számot, melynek multiplicitása k = 1. A Carmichael-sejtés állítása szerint nem is létezik ilyen m.

Ritkán tóciens számok 
A ritkán tóciens számok koncepcióját David Masser és Peter Man-Kit Shiu alkották meg 1986-ban. Megmutatták, hogy minden primoriális ritkán tóciens. 
Egy n természetes szám pontosan akkor ritkán tóciens, ha minden m > n természetes számra:

ahol  az Euler-függvényt jelenti.

Erősen tóciens számok 
Az elgondolás hasonló, mint az erősen összetett számoké: egy erősen tóciens szám (highly totient number) olyan k egész szám, amire több megoldása van a

 φ(x) = k 

egyenletnek – φ az Euler-függvényt jelöli – mint bármely nála kisebb egésznek.  Nagyobb a valenciája vagy multiplicitása, mint a nála kisebb számoknak.

Kotóciens 
Az  szám kotóciense éppen . Értéke megegyezik az -nél nem nagyobb, -nel legalább egy közös prímtényezővel bíró számokéval.

A nonkotóciens számok azok a számok, melyek nem fordulnak elő semmilyen szám kotócienseként sem, tehát az m − φ(m) = n egyenletnek nincs megoldása m-re.

Erősen kotóciens számok 
Egy erősen kotóciens szám (highly cototient number) olyan k>1 egész szám, amire több megoldása van a következő egyenletnek:

x − φ(x) = k,

mint bármely 1<n<k egész szám esetében, tehát ami több számnak kotóciense, mint bármely nála kisebb 1-nél nagyobb egész. Az egyenletben φ az Euler-függvényt jelöli. Mivel a k = 1 esetben az egyenletnek végtelen sok megoldása van, ezért ezt az értéket kihagyták a definícióból.

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.” .
 Néha a Gamma-függvényt is nevezik Euler-féle gammafüggvénynek.
 A Mathematica programban az EulerPhi függvénnyel számolható ki az értéke.

További információk 
 Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat
 Alice és Bob - 21. rész: Alice és Bob titkosít
 Alice és Bob - 26. rész: Alice és Bob átlépi a célvonalat

Jegyzetek

Kapcsolódó szócikkek
 Nontóciens számok

Számelmélet
Számelméleti függvények