Obliczyć φ(n) (funkcja Eulera) dla następujących n:
a) 1024
b) 1031
W jaki sposób "zabrać się" do tego zadnia?
Pozdrawiam
the moon
Oblicz funkcję Eulera dla n...
-
Lady Tilly
- Użytkownik
- Posty: 3807
- Rejestracja: 4 cze 2005, o 10:29
- Płeć: Kobieta
- Lokalizacja: nie wiadomo
- Podziękował: 1 raz
- Pomógł: 712 razy
-
the moon
- Użytkownik
- Posty: 92
- Rejestracja: 8 paź 2004, o 19:54
- Płeć: Mężczyzna
- Lokalizacja: Poland
- Podziękował: 5 razy
Oblicz funkcję Eulera dla n...
Dziękuję za naprowadzenie ale mam pytanie w jaki sposób rozbić np funkcję φ(1031) na "pod funkcje" φ1 * φ2... itd tak, by szybciej zliczało się jej wartość (analizowanie wyłącznie "samej" funkcji φ(1031) zajałoby chyba z 7 dni... ).
Przykład
mam funkcję φ(100) = φ(4 * 25) = φ(4) * φ(25) = 2 * 20 = 40 - takie rozłożenie jest prawidłowe (dlaczego? nie wiem)
ale również dla φ(100) mam
φ(100) = φ(5 * 20) = φ(5) * φ(20) = 4 * 8 = 32 - co jest złym rozwiązaniem
Dla tego samego przykładu otrzymałem dwa różne wyniki 40 (prawidłowy) i 32, co oznacza, że rozkład funkcji φ(n) nie może być przypadkowy. W jaki sposób wywnioskować, który jest tym prawidłowym, dlaczgo właśnie to rozwiązanie?
Przykład
mam funkcję φ(100) = φ(4 * 25) = φ(4) * φ(25) = 2 * 20 = 40 - takie rozłożenie jest prawidłowe (dlaczego? nie wiem)
ale również dla φ(100) mam
φ(100) = φ(5 * 20) = φ(5) * φ(20) = 4 * 8 = 32 - co jest złym rozwiązaniem
Dla tego samego przykładu otrzymałem dwa różne wyniki 40 (prawidłowy) i 32, co oznacza, że rozkład funkcji φ(n) nie może być przypadkowy. W jaki sposób wywnioskować, który jest tym prawidłowym, dlaczgo właśnie to rozwiązanie?
