Eulerjeva funkcija fi: Razlika med redakcijama

Izbrisana vsebina Dodana vsebina

Znotrajvrstično

Trenutna redakcija s časom 20:02, 11. julij 2015

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 = p^m (m ≥ 1) potenca kakega praštevila, velja:

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

Primer: φ(16) = φ( 2⁴) = 2⁴ - 2³ = 16 - 8 = 8, oziroma: φ(16) = φ(2⁴) = 2³ · (2 - 1) = 8 · 1 = 8.

Tuja števila[uredi | uredi kodo]

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

\varphi (ab)=\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) = φ(2² · 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]

Weisstein, Eric Wolfgang. »Totient Function«. MathWorld.

Ta matematični članek je škrbina. Pomagajte Wikipediji in ga razširite.

@@ Vrstica 1: / Vrstica 1: @@
+[[Slika:EulerPhi.svg|thumb|right|250px|Graf prvih tisoč vrednosti funkcije <math>\varphi(n)</math>]]
-'''Eulerjeva fúnkcija &phi;(''n'')''' [''òjlerjeva ~ fí''] je v [[teorija števil|teoriji števil]] [[multiplikativna funkcija|multiplikativna]] [[aritmetična funkcija]] poljubnega [[pozitivno število|pozitivnega]] [[celo število|celega]] [[število|števila]] ''n'' in da skupno število pozitivnih celih števil, ki ne presegajo ''n'', in so ''n'' [[tuje število|tuja]]. Ali drugače rečeno, ki so manjša od ''n'' in so ''n'' relativno [[praštevilo|praštevila]]. Na primer, &phi;([[8 (število)|8]]) = 4, ker so štiri števila, [[1 (število)|1]], [[3 (število)|3]], [[5 (število)|5]] in [[7 (število)|7]] tuja številu 8. [[Funkcija|Funkcijo]] je uvedel in raziskoval [[Švicarji|švicarski]] [[matematik]] [[Leonhard Euler]] in se imenuje po njem. Funkciji rečejo tudi kar '''Eulerjeva funkcija'''. [[Angleži|Angleški]] matematik [[James Joseph Sylvester]] je zanjo leta [[1882]] uvedel ime ''»totientna funkcija«'', kjer je »totient« sestavljenka iz ''tot''alni in kvoc''ient''..
+'''Eulerjeva fúnkcija φ(''n'')''' [òjlerjeva ~ fí] je v [[teorija števil|teoriji števil]] [[multiplikativna funkcija|multiplikativna]] [[aritmetična funkcija]] poljubnega [[pozitivno število|pozitivnega]] [[celo število|celega]] [[število|števila]] ''n'' in da skupno število pozitivnih celih števil, ki ne presegajo ''n'', in so ''n'' [[tuje število|tuja]]. Ali drugače rečeno, ki so manjša od ''n'' in so ''n'' relativno [[praštevilo|praštevila]]. Na primer, φ([[8 (število)|8]]) = 4, ker so štiri števila, [[1 (število)|1]], [[3 (število)|3]], [[5 (število)|5]] in [[7 (število)|7]] tuja številu 8. [[Funkcija|Funkcijo]] je uvedel in raziskoval [[Švicarji|š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 ''tot''alni in kvoc''ient''.
-Eulerjeva funkcija fi je pomembna predvsem, ker da velikost multiplikativne [[matematična grupa|grupe]] celih števil po [[modulska aritmetika|modulu]] ''n'', oziroma natančneje, &phi;(''n'') je [[kardinalno število]] [[enota|enotskih]] grup [[kolobar]]ja '''Z'''/''n'''''Z'''. To dejstvo skupaj z [[Lagrangeev izrek|Lagrangeevim izrekom]] zagotovi dokaz [[Eulerjev izrek|Eulerjevega izreka]].
+Eulerjeva funkcija fi je pomembna predvsem, ker da velikost multiplikativne [[grupa (matematika)|grupe]] celih števil po [[modularna aritmetika|modulu]] ''n'', oziroma natančneje, φ(''n'') je [[kardinalno število]] enotskih grup [[kolobar]]ja '''Z'''/''n'''''Z'''. To dejstvo skupaj z [[Lagrangeev izrek|Lagrangeevim izrekom]] zagotovi dokaz [[Eulerjev izrek|Eulerjevega izreka]].
-== Računanje Eulerjeve funkcije &phi;(''n'') ==
+== Računanje Eulerjeve funkcije φ(''n'') ==
 === Praštevila ===
-Če je ''n'' sámo praštevilo ''p'', velja &phi;(''p'') = ''p'' - 1.
+Če je ''n'' sámo praštevilo ''p'', velja φ(''p'') = ''p'' - 1.
 Primer: φ(19) = 19 - 1 = 18.
@@ Vrstica 15: / Vrstica 16: @@
 Če je ''n'' = ''p''<sup>''m''</sup> (''m'' ≥ 1) [[potenca]] kakega praštevila, velja:
-: <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> &middot; (2 - 1) = 8 &middot; 1 = 8.
+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 ===
@@ Vrstica 23: / Vrstica 24: @@
 Če sta si ''a'' in ''b'' tuji števili, je funkcija multiplikativna in velja:
-: <math> \varphi(a b) = \varphi(a)\varphi(b) \; . </math>
+: <math> \varphi(a b) = \varphi(a)\varphi(b) \!\, . </math>
-Primer: φ(15) = φ(3) &middot; φ(5) = 2 &middot; 4 = 8.
+Primer: φ(15) = φ(3) · φ(5) = 2 · 4 = 8.
-Obe zgornji lastnosti lahko združimo v:
+Obe zgornji značilnosti lahko združimo v:
-: <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> &middot; 3 &middot; 167) = 2004 &middot; (1 - 1/2) &middot; (1 - 1/3) &middot; (1 - 1/167) = 664;
+Primer: φ(2004) = φ(2<sup>2</sup> · 3 · 167) = 2004 · (1 - 1/2) · (1 - 1/3) · (1 - 1/167) = 664;
-== Druge lastnosti ==
+== Druge značilnosti ==
 == Rodovna funkcija ==
 == Obnašanje funkcije ==
+== Nekatere vrednosti funkcije ==
+{| class="wikitable"
-== Vrednosti funkcije ==
+! <math>\varphi(n)</math>
+! +0 || +1 || +2 || +3 || +4 || +5 || +6 || +7 || +8 || +9
-{|
-|
+|-
+! 0+
-{| border="1" cellspacing="0" cellpadding="1" style="background:#f3f9ff;"
+| &nbsp; || 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6
-! bgcolor="#aaaaff" | <math>n</math>
-| 01 || 02 || 03 || 04 || 05 || 06 || 07 || 08 || 09 || 10 || 11 || 12 || 13 || 14 || 15 || 16 || 17 || 18 ||19 || 20
 |-
+!10+
-! bgcolor="#aaaaff" | <math>\phi(n)</math>
-| 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 || 10 || 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8
+|  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
-{| border="1" cellspacing="0" cellpadding="1" style="background:#f3f9ff;"
-! bgcolor="#aaaaff" | <math>n</math>
-| 21 || 22 || 23 || 24 || 25 || 26 || 27 || 28 || 29 || 30 || 31 || 32 || 33 || 34 || 35 || 36 || 37 || 38 ||39 || 40
 |-
+!40+
-! bgcolor="#aaaaff" | <math>\phi(n)</math>
-| 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8 || 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16
+| 16 || 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42
-|}
 |-
+!50+
-|
+| 20 || 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58
-{| border="1" cellspacing="0" cellpadding="1" style="background:#f3f9ff;"
-! bgcolor="#aaaaff" | <math>n</math>
-| 41 || 42 || 43 || 44 || 45 || 46 || 47 || 48 || 49 || 50 || 51 || 52 || 53 || 54 || 55 || 56 || 57 || 58 ||59 || 60
-|-
-! bgcolor="#aaaaff" | <math>\phi(n)</math>
-| 40 || 12 || 42 || 20 || 24
-| 22 || 46 || 16 || 42 || 20 || 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16
-|}
 |-
+!60+
-|
+| 16 || 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44
-{| border="1" cellspacing="0" cellpadding="1" style="background:#f3f9ff;"
-! bgcolor="#aaaaff" | <math>n</math>
-| 61 || 62 || 63 || 64 || 65 || 66 || 67 || 68 || 69 || 70 || 71 || 72 || 73 || 74 || 75 || 76 || 77 || 78 || 79 || 80
 |-
+!70+
-! bgcolor="#aaaaff" | <math>\phi(n)</math>
-| 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 || 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32
+| 24 || 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78
-|}
 |-
+!80+
-|
+| 32 || 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88
-{| border="1" cellspacing="0" cellpadding="1" style="background:#f3f9ff;"
-! bgcolor="#aaaaff" | <math>n</math>
-| 81 || 82 || 83 || 84 || 85 || 86 || 87 || 88 || 89 || 90 || 91 || 92 || 93 || 94 || 95 || 96 || 97 || 98 || 99 || 00
 |-
+!90+
-! bgcolor="#aaaaff" | <math>\phi(n)</math>
-| 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88 || 24 || 72 || 44 || 60 || 46 || 72 ||  32 || 96 || 42 || 60 || 40
+| 24 || 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60
-|}
 |}
+== Zunanje povezave ==
+* {{MathWorld|urlname=TotientFunction|title=Totient Function}}
 {{math-stub}}
-[[Kategorija:Matematične funkcije]]
+[[Kategorija:Specialne funkcije]]
+[[Kategorija:Multiplikativne funkcije]]
 [[Kategorija:Teorija števil]]
 [[Kategorija:Leonhard Euler]]
-[[bg:Функция на Ойлер]]
-[[ca:Funció Fi d'Euler]]
-[[cs:Eulerova funkce]]
-[[cy:Ffwythiant φ Euler]]
-[[da:Eulers totientfunktion]]
-[[de:Eulersche φ-Funktion]]
-[[en:Euler's totient function]]
-[[es:Función φ de Euler]]
-[[fi:Eulerin φ-funktio]]
-[[fr:Indicatrice d'Euler]]
-[[he:פונקציית אוילר]]
-[[hu:Euler-függvény]]
-[[it:Funzione phi di Eulero]]
-[[ja:オイラーのφ関数]]
-[[ko:오일러 파이 함수]]
-[[nl:Indicator (getaltheorie)]]
-[[pl:Funkcja φ]]
-[[pt:Função totiente de Euler]]
-[[ru:Функция Эйлера]]
-[[sr:Ојлерова фи функција]]
-[[sv:Eulers fi-funktion]]
-[[tr:Totient]]
-[[zh:欧拉函数]]