Eulerjeva funkcija fi

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Graf prvih tisoč vrednosti funkcije \varphi(n)

Eulerjeva fúnkcija φ(n) [òjlerjeva ~ fí] je v teoriji števil multiplikativna aritmetična funkcija poljubnega pozitivnega celega števila n in da skupno število pozitivnih celih števil, ki ne presegajo n, in so n tuja. Ali drugače rečeno, ki so manjša od n in so n relativno praštevila. Na primer, φ(8) = 4, ker so štiri števila, 1, 3, 5 in 7 tuja številu 8. Funkcijo je uvedel in raziskoval švicarski matematik Leonhard Euler in se imenuje po njem. Funkciji rečejo tudi kar Eulerjeva funkcija. Angleški matematik James Joseph Sylvester je zanjo leta 1882 uvedel ime »totientna funkcija«, kjer je »totient« sestavljenka iz totalni in kvocient.

Eulerjeva funkcija fi je pomembna predvsem, ker da velikost multiplikativne grupe celih števil po modulu n, oziroma natančneje, φ(n) je kardinalno število enotskih grup kolobarja Z/nZ. To dejstvo skupaj z Lagrangeevim izrekom zagotovi dokaz Eulerjevega izreka.

Računanje Eulerjeve funkcije φ(n)[uredi | uredi kodo]

Praštevila[uredi | uredi kodo]

Če je n sámo praštevilo p, velja φ(p) = p - 1.

Primer: φ(19) = 19 - 1 = 18.

Potence praštevil[uredi | uredi kodo]

Če je n = pm (m ≥ 1) potenca kakega praštevila, velja:

 \varphi(n) = \varphi(p^{m}) = p^{m} - p^{m-1} = p^{m-1}(p-1) \!\, .

Primer: φ(16) = φ( 24) = 24 - 23 = 16 - 8 = 8, oziroma: φ(16) = φ(24) = 23 · (2 - 1) = 8 · 1 = 8.

Tuja števila[uredi | uredi kodo]

Če sta si a in b tuji števili, je funkcija multiplikativna in velja:

 \varphi(a b) = \varphi(a)\varphi(b) \!\, .

Primer: φ(15) = φ(3) · φ(5) = 2 · 4 = 8.

Obe zgornji značilnosti lahko združimo v:

 \varphi(n) = n \prod_{p | n} \left(1 - {1\over p} \right) \!\, .

Primer: φ(2004) = φ(22 · 3 · 167) = 2004 · (1 - 1/2) · (1 - 1/3) · (1 - 1/167) = 664;

Druge značilnosti[uredi | uredi kodo]

Rodovna funkcija[uredi | uredi kodo]

Obnašanje funkcije[uredi | uredi kodo]

Nekatere vrednosti funkcije[uredi | uredi kodo]

\varphi(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

Zunanje povezave[uredi | uredi kodo]