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^{{\mathrm{\alpha <!--\; \alpha \; -->}}_1}{p}_2^{{\mathrm{\alpha <!--\; \alpha \; -->}}_2}...p_m^{}}$Információ forrás: https://hu.wikipedia.org/wiki/Euler-függvény
  A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.

  ---