MetaMath '25 - Školjka

Vrijeme: 17:27

Eulerova funkcija

Za složene brojeve $n$ , broj različitih ostataka dok ne dođemo do kraja ciklusa je općenito jednak vrijednosti $\varphi(n)$ (vidi dolje za definiciju Eulerove funkcije). Iz potpunog skupa ostataka ${1, 2, \ldots, n-1}$ jednostavno smo, osim nule, izbacili sve one koji nisu relativno prosti s $n$ . Ako počnemo od nekog broja koji je relativno prost s $n$ , i množimo ga relativno prostim brojem, logički se može zaključiti da nikada nećemo dotaknuti broj koji nije relativno prost s $n$ . Sve koji nisu relativno prosti smo maknuli iz skupa $\{1, 2, 3, \ldots, n-1 \}$ i preostalo nam je $\varphi(n)$ brojeva.

Eulerova funkcija

Eulerova funkcija je funkcija $\varphi(n)$ (čita se fi od n) koja svakom prirodnom broju $n > 1$ pridružuje broj relativno prostih brojeva s $n$ koji su manji od $n$ . Posebno je definirano $\varphi(1) = 1$ .

Na primjer: $\varphi(12) = 4$ , od brojeva $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ i $11$ , samo su $1, 5, 7$ i $11$ relativno prosti s $12$ .

Korisna svojstva Eulerove funkcije:

$\varphi(p) = p-1$ za prosti broj $p$

$\varphi(m)\cdot \varphi(n) = \varphi(mn)$ za relativno proste $m, n \in \mathbb{N}$

$\varphi(p^k) = p^k - p^{k-1}$

$\sum\limits_{d|n} \varphi(d) = n$ (za sve djelitelje $d_i$ broja $n$ vrijedi $\varphi(d_1) + \varphi(d_2) + \hdots + \varphi(d_k) = n$ )

Korolar: Ako je rastav broja $n$ na proste faktore $p_1^{\alpha_1}p_2^{\alpha_2}\hdots p_m^{\alpha_m}$ , tada je $\varphi(n) = n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dots\left(1-\frac1{p_m}\right)$

Ovaj korolar može se dokazati i kombinatornim prebrojavanjem, npr. ako je $S = \{1, 2, \hdots, n\}$ i za svaki prosti djelitelj $p_i$ od $n$ definiramo $A_i = \{x \in S : p_i | x\}$ , tada je $\varphi(n) = \left|S\right| - \left|A_1 \cup A_2 \cup \dots \cup A_k \right|$

Primjer 3. Odredi $\varphi(300)$ .

Rješenje:

Faktoriziramo $300 = 2^2 \cdot 3 \cdot 5^2$ . Izračunamo $\varphi(300) = 300\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right) = 300\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{4}{5} = 80$

Kao rješenje ovog zadatka izračunaj i upiši $\varphi(16)$ .

Vratimo se na diskusiju s početka. Analizirali smo što se događa kad računamo potencije modulo neki prosti broj. Što ako modulus $n$ nije prost? Tada će, jasno, biti manje od $n-1$ brojeva u skupu ostataka. Promatrat ćemo samo potencije brojeva koji su relativno prosti s $n$. Pogledajmo potencije broja $2$ modulo $9$: \\ $2^1 \equiv 2$ \\ $2^2 \equiv 4$ \\ $2^3 \equiv 8$ \\ $2^4 \equiv 16 \equiv 7$ \\ $2^5 \equiv 14 \equiv 5$ \\ $2^6 \equiv 10 \equiv 1$ \\ i to je kraj ciklusa, odavde će se ostaci samo ponavljati. Za složene brojeve $n$, broj različitih ostataka dok ne dođemo do kraja ciklusa je općenito jednak vrijednosti $\varphi(n)$ (vidi dolje za definiciju Eulerove funkcije). Iz potpunog skupa ostataka ${1, 2, \ldots, n-1}$ jednostavno smo, osim nule, izbacili sve one koji nisu relativno prosti s $n$. Ako počnemo od nekog broja koji je relativno prost s $n$, i množimo ga relativno prostim brojem, logički se može zaključiti da nikada nećemo dotaknuti broj koji nije relativno prost s $n$. Sve koji nisu relativno prosti smo maknuli iz skupa $\{1, 2, 3, \ldots, n-1 \}$ i preostalo nam je $\varphi(n)$ brojeva. [quote] [b]Eulerova funkcija[/b] Eulerova funkcija je funkcija $\varphi(n)$ (čita se \textit{fi} od \textit{n}) koja svakom prirodnom broju $n > 1$ pridružuje broj relativno prostih brojeva s $n$ koji su manji od $n$. Posebno je definirano $\varphi(1) = 1$. Na primjer: $\varphi(12) = 4$, od brojeva $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ i $11$, samo su $1, 5, 7$ i $11$ relativno prosti s $12$. [/quote] [b]Korisna svojstva Eulerove funkcije:[/b] [quote] $\varphi(p) = p-1$ za prosti broj $p$\\\\ $\varphi(m)\cdot \varphi(n) = \varphi(mn)$ za relativno proste $m, n \in \mathbb{N}$\\\\ $\varphi(p^k) = p^k - p^{k-1}$\\\\ $\sum\limits_{d|n} \varphi(d) = n$ (za sve djelitelje $d_i$ broja $n$ vrijedi $\varphi(d_1) + \varphi(d_2) + \hdots + \varphi(d_k) = n$)\\\\ [/quote] [quote] [b]Korolar:[/b] Ako je rastav broja $n$ na proste faktore $p_1^{\alpha_1}p_2^{\alpha_2}\hdots p_m^{\alpha_m}$, tada je $$\varphi(n) = n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dots\left(1-\frac1{p_m}\right)$$ [/quote] Ovaj korolar može se dokazati i kombinatornim prebrojavanjem, npr. ako je $S = \{1, 2, \hdots, n\}$ i za svaki prosti djelitelj $p_i$ od $n$ definiramo $A_i = \{x \in S : p_i | x\}$, tada je $\varphi(n) = \left|S\right| - \left|A_1 \cup A_2 \cup \dots \cup A_k \right|$ \\ \\ [b]Primjer 3.[/b] Odredi $\varphi(300)$. [b]Rješenje:[/b] Faktoriziramo $300 = 2^2 \cdot 3 \cdot 5^2$. Izračunamo $$\varphi(300) = 300\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right) = 300\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{4}{5} = 80$$ Kao rješenje ovog zadatka izračunaj i upiši $\varphi(16)$.