Oblicz funkcję Eulera (1520)
niczek : Obliczyć φ(1520)
Wiem, że na początek rozkład:
1520 | 2
760 | 2
380 | 2
190 | 2
95 | 5
19 | 19
1
φ(1520) = tutaj już nie wiem. Próbowałem tutaj różne cuda, ale ani razu nie wyszło 1520. Dodam,
że Nie chcę samego rozwiązania − bo to nie jest praca domowa. Chcę to zrozumieć.
27 lis 22:58
niczek :
27 lis 23:37
Jack:
To szło chyba jakoś tak (zakładam, że rozkład jest ok):
1520= 2
4*5*19
Żeby zrozumieć zobacz tutaj:
http://pl.wikipedia.org/wiki/Funkcja_φ
φ(1520)=φ(2
4*5*19)=φ(2
4)*φ(5)*φ(19)=(2
4−2
3)*(5−1)*(19−1)=...
27 lis 23:45
niczek : Rozkład jest dobry.
Można jaśniej od:
(2
4−2
3)*(5−1)*(19−1)=... ?
Na wiki czytałem, zanim napisałem temat...
28 lis 19:00
niczek :
28 lis 19:22
niczek : Rozumiem, że trzeba odjąć 1... ale 23 ≠ 1
28 lis 19:23
niczek :
28 lis 20:04
niczek :
28 lis 20:26
Jack:
jesli n=pk to φ(n) liczymy z takiego wzoru φ(n)=φ(pk)=(pk−pk−1)
Z kolei jeśli NWD(a,b)=1, to zachodzi multiplikatywność funkcji Eulera, czyli φ(ab)=φ(a)*φ(b).
28 lis 20:33