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.

Az Euler-féle φ-függvény grafikonja

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

  01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  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
  26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
  12 18 12 28 8 30 16 20 16 24 12 36 18 24 16 40 12 42 20 24 22 46 16 42 20
  51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
  32 24 52 18 40 24 36 28 58 16 60 30 36 32 48 20 66 32 44 24 70 24 72 36 40
  76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
  36 60 24 78 32 54 40 82 24 64 42 56 40 88 24 72 44 60 46 72 32 96 42 60 40

Legfontosabb tulajdonságai szerkesztés

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

  • 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 szerkesztés

 

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

 

Tóciens számok szerkesztés

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).[1] 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,[2] és minden páratlan számnak létezik páros, nontóciens többszöröse.[3]

Az x-nél kisebb tóciens számok határértéke

 ,

ahol a konstans C = 0,8178146... .[4]

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

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

Ford tétele szerkesztés

(Ford 1999) 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,[8] Schinzel H hipotézise folyományaként.[4] Valóban, minden előforduló multiplicitás végtelen sokszor is előfordul.[4][7]

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

Ritkán tóciens számok szerkesztés

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

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

Kotóciens szerkesztés

Az n szám kotóciense éppen n − φ(n). Értéke megegyezik az n-nél nem nagyobb, n-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 szerkesztés

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

  • 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 szerkesztés

Jegyzetek szerkesztés

  1. Guy (2004) p.144
  2. Sándor & Crstici (2004) p.230
  3. Zhang, Mingzhi (1993). „On nontotients”. Journal of Number Theory 43, 168–172. o. DOI:10.1006/jnth.1993.1014. ISSN 0022-314X.  
  4. a b c Ford, Kevin (1998). „The distribution of totients”. Ramanujan J. 2, 67–151. o. DOI:10.1007/978-1-4757-4507-8_8. ISSN 1382-4090.  
  5. Sándor et al (2006) p.22
  6. Sándor et al (2006) p.21
  7. a b Guy (2004) p.145
  8. Sándor & Crstici (2004) p.229
  9. Sándor & Crstici (2004) p.228
  10. MathWorld: Totient Valence Function

Kapcsolódó szócikkek szerkesztés