Euler-függvény

A Wikipédiából, a szabad lexikonból.

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.

Legelemibb meghatározása, hogy egy adott egész számhoz a nála kisebb relatív prím pozitív egész számok számát adja meg.

Formálisan:

$\varphi(n) = \left| \left\{ k \in \mathbb{Z} \ | \ 0 < k \le n \ \wedge \ \left( n, k \right) = 1 \right\} \right| \ \ \ \left( n \in \mathbb{N} \right)$ .

Egy másik, de fentivel teljességgel azonos függvényt adó értelmezésben e függvény az n-hez redukált maradékosztályok számát adja meg (ez gyakorlatilag ugyanaz, mint az előbbi definíció, elvontaban, 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.

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

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

$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
$φ(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
$φ(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
$φ(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	00
$φ(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

[szerkesztés] Legfontosabb tulajdonságai

[szerkesztés] 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:

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

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

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) } =$ $= p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} ... p_{m}^{\alpha_{m}} \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ó.

[szerkesztés] Az osztókra összeadva

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

[szerkesztés] Összegfüggvénye

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

[szerkesztés] 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." .
Máig megoldatlan a következő probléma, a Carmichael-sejtés: „Az Euler-függvény minden értéket legalább két helyen vesz fel.”
Néha a Gamma-függvényt is nevezik Euler-féle gammafüggvénynek.