Eulerjeva funkcija fi: Razlika med redakcijama
m slog |
m pp |
||
Vrstica 6: | Vrstica 6: | ||
== Računanje Eulerjeve funkcije φ(''n'') == |
== Računanje Eulerjeve funkcije φ(''n'') == |
||
=== Praštevila === |
=== Praštevila === |
||
Vrstica 19: | Vrstica 18: | ||
: <math> \varphi(n) = \varphi(p^{m}) = p^{m} - p^{m-1} = p^{m-1}(p-1) \!\, . </math> |
: <math> \varphi(n) = \varphi(p^{m}) = p^{m} - p^{m-1} = p^{m-1}(p-1) \!\, . </math> |
||
Primer: φ(16) = φ( 2<sup>4</sup>) = 2<sup>4</sup> - 2<sup>3</sup> = 16 - 8 = 8, oziroma: φ(16) = φ(2<sup>4</sup>) = 2<sup>3</sup> |
Primer: φ(16) = φ( 2<sup>4</sup>) = 2<sup>4</sup> - 2<sup>3</sup> = 16 - 8 = 8, oziroma: φ(16) = φ(2<sup>4</sup>) = 2<sup>3</sup> · (2 - 1) = 8 · 1 = 8. |
||
=== Tuja števila === |
=== Tuja števila === |
||
Vrstica 27: | Vrstica 26: | ||
: <math> \varphi(a b) = \varphi(a)\varphi(b) \!\, . </math> |
: <math> \varphi(a b) = \varphi(a)\varphi(b) \!\, . </math> |
||
Primer: φ(15) = φ(3) |
Primer: φ(15) = φ(3) · φ(5) = 2 · 4 = 8. |
||
Obe zgornji lastnosti lahko združimo v: |
Obe zgornji lastnosti lahko združimo v: |
||
Vrstica 33: | Vrstica 32: | ||
: <math> \varphi(n) = n \prod_{p | n} \left(1 - {1\over p} \right) \!\, . </math> |
: <math> \varphi(n) = n \prod_{p | n} \left(1 - {1\over p} \right) \!\, . </math> |
||
Primer: φ(2004) = φ(2<sup>2</sup> |
Primer: φ(2004) = φ(2<sup>2</sup> · 3 · 167) = 2004 · (1 - 1/2) · (1 - 1/3) · (1 - 1/167) = 664; |
||
== Druge lastnosti == |
== Druge lastnosti == |
||
== Rodovna funkcija == |
== Rodovna funkcija == |
||
== Obnašanje funkcije == |
== Obnašanje funkcije == |
||
== Nekatere vrednosti funkcije == |
== Nekatere vrednosti funkcije == |
||
Vrstica 77: | Vrstica 73: | ||
| 24 || 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 |
| 24 || 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 |
||
|} |
|} |
||
{{math-stub}} |
{{math-stub}} |
Redakcija: 11:33, 16. januar 2009
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)
Praštevila
Če je n sámo praštevilo p, velja φ(p) = p - 1.
Primer: φ(19) = 19 - 1 = 18.
Potence praštevil
Če je n = pm (m ≥ 1) potenca kakega praštevila, velja:
Primer: φ(16) = φ( 24) = 24 - 23 = 16 - 8 = 8, oziroma: φ(16) = φ(24) = 23 · (2 - 1) = 8 · 1 = 8.
Tuja števila
Če sta si a in b tuji števili, je funkcija multiplikativna in velja:
Primer: φ(15) = φ(3) · φ(5) = 2 · 4 = 8.
Obe zgornji lastnosti lahko združimo v:
Primer: φ(2004) = φ(22 · 3 · 167) = 2004 · (1 - 1/2) · (1 - 1/3) · (1 - 1/167) = 664;
Druge lastnosti
Rodovna funkcija
Obnašanje funkcije
Nekatere vrednosti funkcije
+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 |