Euler-függvény

A Wikipédiából, a szabad enciklopédiából
Az Euler-féle φ-függvény grafikonja

A  \varphi(n) -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:

φ(n) = |{ k∈Z | 0<k≤n (n,k) = 1 }|   (ahol n∈N) .

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.

Értékei kis számokra[szerkesztés]

n 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
\phi(n) 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
n 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
\phi(n) 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
n 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
\phi(n) 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
n 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
\phi(n) 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:

 \forall a,b \in \mathbb{Z}: \ \left( \ \ \left(a,b\right)=1 \ \Rightarrow \ \varphi(ab) = \varphi(a) \cdot \varphi(b) \ \right)

Például:

  • a=7 az prím szám, és \varphi(7)=6
  • b=11 szintén prím, és \varphi(11)=10

(lásd az Értékei kis számokra c. táblázatot)

A két prímszám szorzata: 7\cdot 11=77, valamint \varphi(77)=60, ami pontosan 6\cdot 10.

Kiszámítása[szerkesztés]

  • Viszonylag könnyű belátni a következőket:
    • Ha  n=p prímszám, akkor  \varphi(p) = p-1 (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  n=p^{\alpha} \ \ \ (\alpha \in \mathbb{Z}^{+}) prímhatvány, akkor  \varphi(p^{\alpha}) = p^{\alpha}-p^{\alpha -1} = p^{\alpha}\left( 1-\frac{1}{p} \right)
  • Á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  n = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{m}^{\alpha_{m}} = \prod_{i=1}^{m}{p_{i}^{\alpha_{i}}} ,  m \in \mathbb{N}^{+} , \ \forall i \in \left\{ 1,2,.,...,m \right\} : \left( \alpha_{i} \in \mathbb{N}^{+} \right) , és  p_{i} (páronként) különböző prímek, akkor érvényes
 \varphi(n) = n \cdot \prod_{i=1}^m { \left( 1-\frac{1}{p_{i}} \right) } =
 = n \left( 1-\frac{1}{p_{1}} \right) \left( 1-\frac{1}{p_{2}} \right) ... \left( 1-\frac{1}{p_{m}} \right) , feltéve hogy  \left( n>1 \right)

ahol tehát  m az  n szám különböző prímtényezőinek száma,  p_{i} 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

\varphi(n)=n\sum_{d\vert n}\frac{\mu(d)}{d}

alakban írható.

Az osztókra összeadva[szerkesztés]

\sum_{d|n}\varphi(d)=n

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

\frac{1}{n},\frac{2}{n},\dots,\frac{n}{n}

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.

Összegfüggvénye[szerkesztés]

\sum_{n=1}^{x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\log x)

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

\frac{x}{\log x}\exp\left({ (C+o(1))(\log\log\log x)^2 }\right) \ ,

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:

\vert\{ n : \phi(n) \le x \}\vert = \frac{\zeta(2)\zeta(3)}{\zeta(6)} \cdot x + R(x) \ ,

ahol az R hibatag nagyságrendje legfeljebb x / (\log x)^k 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]

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.

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

Kapcsolódó szócikkek[szerkesztés]