Eulerjeva funkcija

Ko tudi učitelj ne more pomagati...
Odgovori
yocker
Prispevkov: 40
Pridružen: 8.9.2004 21:58
Kraj: krško

Eulerjeva funkcija

Odgovor Napisal/-a yocker »

Zanima me kako se zracuna npr. fi(7000)? Oziroma za vsa tako velika števila.
Upam da sem na pravem forumu :)

Hvala!

Uporabniški avatar
shrink
Prispevkov: 14610
Pridružen: 4.9.2004 18:45

Re: Eulerjeva funkcija

Odgovor Napisal/-a shrink »

yocker napisal/-a:Zanima me kako se zracuna npr. fi(7000)? Oziroma za vsa tako velika števila.
Upam da sem na pravem forumu :)

Hvala!
Obstaja (Eulerjeva) formula, s katero je možno izračunati vrednost Eulerjeve funkcije za poljubno naravno število \(m\):

\(\phi(m) = m(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) \ldots (1 - \frac{1}{p_k})\),

pri čemer je:

\(m = p_1^{a_1}p_2^{a_2} \ldots p_k^{a_k}\) (zapis oz. razcep naravnega števila kot produkt potenc praštevil).

V tvojem primeru pride:

\(7000 = 2^3 \cdot 5^3 \cdot 7\)

in od tod:

\(\phi(7000) = 7000 \cdot (1 - \frac{1}{2}) \cdot (1 - \frac{1}{5}) \cdot (1 - \frac{1}{7}) = 2400\).

Za izpeljavo te formule glej npr.: http://www.cut-the-knot.org/blue/Euler.shtml.

yocker
Prispevkov: 40
Pridružen: 8.9.2004 21:58
Kraj: krško

Odgovor Napisal/-a yocker »

Hvala! :mrgreen:

azi
Prispevkov: 74
Pridružen: 23.10.2005 14:07

Odgovor Napisal/-a azi »

Druga fora je da vzames faktorje stevila in se drzis pravil :


phi(a*b) = phi(a) * phi(b) vsakic ko je gcd(a,b) = 1, ter

phi(p^n) = p^n - p^(n-1) za vsako prastevilo p.

za stevilo 20 torej dobis :

phi(20) = phi(5) * phi(2^2) = 4*2 = 8

seveda, pa je faktorizacija sama po sebi tudi kar potratna operacija in je zato zgorni
primer uporaben le za manjsa stevila..

kresnicka006
Prispevkov: 6
Pridružen: 29.8.2011 20:11

Re: Eulerjeva funkcija

Odgovor Napisal/-a kresnicka006 »

Kako se pa pri Eulerjevi funkciji lotim reševanja enačbe? Npr.

\(\phi(n) = 4\)

?

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Re: Eulerjeva funkcija

Odgovor Napisal/-a Aniviller »

Ce je n prastevilo, je \(\phi(n)=n-1\), s tem dobis resitev n=5.
Ce je n sestavljeno, potem lahko razbijes na produkt:
\(\phi(\prod p_i^{k_i})=\prod\phi(p_i^{k_i})\)
kjer je \(\phi(p^k)=p^{k-1}(p-1)\). Pogoj je, da vsi ti faktorji delijo 4. Ostanejo ti torej samo kombinacije z n=5 (fi=4), n=3 (fi=2), n=2 (fi=1), n=4 (fi=2) in n=8(fi=4). Iz teh lahko sestavis s produkti (samo razlicne smes mnozit, isti so ze vsteti v potenciranju):
5=5
8=8
10=5*2
12=4*3

Odgovori