Suradnik10: /* Osnovna svojstva */

2026-04-12T03:55:14Z

Osnovna svojstva

←Starija inačica		Inačica od 12. travanj 2026. u 03:55
Redak 10:		Redak 10:

	== Osnovna svojstva ==		== Osnovna svojstva ==
	▪Eulerova funkcija je ''multiplikativna'', odnosno vrijedi <math> \varphi{(mn)} = \varphi(m)\varphi(n)</math><ref>Geometrijski dokaz ~~se može naći~~ na ~~poveznici~~ http://e.math.hr/Vol31/Bokun</ref>,		▪Eulerova funkcija je ''multiplikativna'', odnosno vrijedi <math> \varphi{(mn)} = \varphi(m)\varphi(n)</math><ref>Geometrijski dokaz je na Mirela Jukić Bokun i Andrea Behin: [http://e.math.hr/Vol31/Bokun ''Eulerova funkcija'']. math.e. br. 31. </ref>,

	▪<math> \varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1},</math>		▪<math> \varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1},</math>

WikiSysop: Bot: Automatski unos stranica

2021-12-10T17:23:22Z

Bot: Automatski unos stranica

Nova stranica

'''Eulerova funkcija''' je [[Funkcija (matematika)|funkcija]] koja svakom [[Prirodni brojevi|prirodnom broju]] <math>n</math> pridružuje broj [[prosti brojevi|relativno prostih]] s <math> n </math> koji su manji od <math> n </math> (ili jednaki kada je <math> n = 1 </math>). Označavamo ju s <math> \varphi{(n)} </math>.<ref>Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.</ref>

Primjerice, <math> \varphi(2) = 1, \varphi(6) = 2, \varphi(11) = 10, </math> itd.

Uočimo da je <math> \varphi(1) = 1, \varphi(p) = p - 1 </math> gdje je <math> p </math> bilo koji prosti broj.

Skup relativno prostih brojeva s <math> n </math> u <math> \{1, 2, ... n\} </math> označavat ćemo sa <math> S_n </math>.

Ovu je funkciju [[1763.]] uveo znameniti [[Švicarska|švicarski]] matematičar [[Leonhard Euler]].

== Osnovna svojstva ==
▪Eulerova funkcija je ''multiplikativna'', odnosno vrijedi <math> \varphi{(mn)} = \varphi(m)\varphi(n)</math><ref>Geometrijski dokaz se može naći na poveznici http://e.math.hr/Vol31/Bokun</ref>,

▪<math> \varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1},</math>

▪ Vrijedi <math>\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),</math>

▪ Vrijedi <math> \sum_{d \mid n}\varphi(d) = n </math> ([[Gaussova lema o Eulerovoj funkciji]]).

== Struktura skupa <math> S_n </math> ==

Uzmimo <math> n = 20. </math> Navodimo skup <math> S_{20} </math> relativno prostih brojeva s 20 manjih od 20:

<math> S_{20} = \{1, 3, 7, 9, 11, 13, 17, 19\}. </math>

Uočimo da je <math> 1 + 19 = 3 + 17 = 7 + 13 = 9 + 11 = 20. </math>

Pretpostavljamo da struktura skupa <math> S_{n} = \{k_1 = 1, k_2, ..., k_r = n - 1\} </math> ima sljedeću invarijantu: <math> k_i + k_{n - i} = n, \forall i = 1, 2, ..., r. </math>

Sada ćemo tvrdnju ovog naslućivanja i dokazati. Neka je <math> k \in \mathbb{N} </math> takav da <math> M(k, n) = 1. </math> Želimo pokazati da je tada nužno <math> M(n - k, n) = 1. </math> Pretpostavimo da je <math> M(n - k, n) = d > 1. </math> To bi značilo da <math> d|n, d | n - k. </math> Da bi izraz <math> n - k </math> bio djeljiv s <math> d </math> mora biti <math> d|k. </math> To povlači <math> d = 1, </math> što je i trebalo dokazati.

Zato je za <math> n \geq 3 </math> kardinalnost skupova <math> S_n </math> paran broj, a znamo da je <math> \varphi(1) = \varphi(2) = 1. </math>

=== Dodatna svojstva djeljivosti elemenata skupa <math>S_n</math> ===
Isto tako, treba uočiti da vrijedi sljedeće.

==== Ako je <math>n</math> paran ====
Ako je dakle <math>n = 2k</math>, tada je razlika bilo koja dva člana skupa <math>S_{2n}</math> paran broj. Ovo slijedi iz činjenice da je očito svaki element skupa <math>S_{2n}</math> neparan. Primjerice <math>S_{4} = \{1, 3, 7, 9\}</math> te <math>S_{12} = \{1, 5, 7, 11\} </math>.

==== Ako je <math>n</math> neparan ====
Ako je pak <math>n = 2k + 1</math>, primijetimo da razlike elemenata skupa <math>S_{2n}</math> ne moraju nužno sve biti parne, ali s druge strane <math>k, k + 1</math> su članovi skupa <math>S_{2n}</math> (pa je njihova razlika najmanji neparni broj, broj <math>1</math>), tj. mora biti <math>M(2k + 1, k) = M(2k + 1, k + 1) = 1.</math> Naime, iz <math>M(k + (k + 1), k) = d</math> slijedi <math>d | k + 1</math>. No, kako <math>d|k, d|k + 1 </math> slijedi <math>d = 1</math> jer je <math>M(k, k + 1) = 1</math>. (1)

Svojstvo <math> M(2k + 1, k + 1) = 1</math> je ekvivalento s <math> M(2k + 1, 2k + 1 - k) = 1</math> pa, zbog (1), ono vrijedi. Primjer ovakvog skupa bio bi <math>S_{9} = \{1, 2, 4, 5, 7, 8\}</math> te primjerice <math>S_{15} = \{1, 2, 4, 7, 8, 11, 13, 14\} </math>.

==Izvori==
{{izvori}}

[[Kategorija:Algebra]]

Eulerova funkcija - Povijest promjena

Suradnik10: /* Osnovna svojstva */

WikiSysop: Bot: Automatski unos stranica