Euler-függvény

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

A ${\displaystyle \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:

${\displaystyle \varphi (n)=|\{k\in \mathbb {Z} |0<k\leq n\wedge (n,k)=1\}|\quad ({\text{ahol}}\ n\in \mathbb {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.

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

Értékei kis számokra

${\displaystyle 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 ${\displaystyle \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

${\displaystyle 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 ${\displaystyle \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

${\displaystyle 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 ${\displaystyle \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

${\displaystyle 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 ${\displaystyle \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

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:

${\displaystyle \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 ${\displaystyle \varphi (7)=6}$
• b=11 szintén prím, és ${\displaystyle \varphi (11)=10}$

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

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

Kiszámítása

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

${\displaystyle \varphi (n)=n\cdot \prod _{i=1}^{m}{\left(1-{\frac {1}{p_{i}}}\right)}=}$ ${\displaystyle =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 ${\displaystyle \left(n>1\right)}$

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

${\displaystyle \varphi (n)=n\sum _{d\vert n}{\frac {\mu (d)}{d}}}$

alakban írható.

Az osztókra összeadva

${\displaystyle \sum _{d|n}\varphi (d)=n}$

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

${\displaystyle {\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 ${\displaystyle (a,d)=1}$. Innen adódik a kívánt azonosság.

Összegfüggvénye

${\displaystyle \sum _{n=1}^{x}\varphi (n)={\frac {3}{\pi ^{2}}}x^{2}+O(x\log x)}$

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).^[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

${\displaystyle {\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:

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

ahol az R hibatag nagyságrendje legfeljebb ${\displaystyle 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

(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

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:

${\displaystyle \varphi (m)>\varphi (n),}$

ahol ${\displaystyle \varphi }$ 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.^[10]

Kotóciens

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

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

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. 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. 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

• Nontóciens számok