Matematyka.pl

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

punkt trzeci

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?

Czynniki muszą być względnie pierwsze.
... i%20Eulera