Problem w zrozumieniu twierdzenia Eulera Mateusz: Czytam obecnie materiały dotyczące twierdzenia Eulera i nie mogę zrozumieć jednej rzeczy, ale bardzo istotnej. Dlaczego φ(16) = 8? Jak rozumiem, aby móc obliczyć powyższe równanie należy liczbę 16 rozłożyć na iloczyn liczb pierwszych które są dzielnikami 16, więc otrzymamy 16 = 2² * 2² A wtedy φ(16) = 16 * (1 − 1/2) * (1 − 1/2) Ale wtedy φ(16) = 4 W którym miejscu popełniam błąd? I jeszcze jedno − czy jest jakiś sposób na szybkie wyznaczenie liczb pierwszych, za pomocą których można zapisać np. liczbę 2006? Z tego co wiem to chyba nie, bo między innymi na tym zagadnieniu bazuje RSA, ale wolę się upewnić. Bardzo proszę o pomoc.

Basia: 16 = 2⁴ φ(16) = 16*(1−¹₂) = 8 patrz: http://pl.wikipedia.org/wiki/Funkcja_%CF%86

Mateusz: No właśnie tak się zastanawiałem czy wykładnikiem potęgi może być liczba złożona. Uznałem, że nie, ale jak widać mogą. Dzięki za ten link, poczytałem i już nie pytam dlaczego φ(23) = 22. A jeżeli na sprawdzianie dostanę liczbę 2006 to mam po kolei wszystkie liczby pierwsze sprawdzać?

Vax: 16 = 2⁴, rozkładając liczbę na czynniki pierwsze rozkładamy je tak, żeby kolejne czynniki były różnymi liczbami pierwszymi, tj bierzemy maksymalne wykładniki w których występują dane liczby

	1
pierwsze. Wówczas φ(16) = 16 * (1−		) = 8.
	2

Proponuję jednak po prostu zapamiętać wzór φ(p^k) = p^k−1(p−1), wówczas korzystając z multiplikatywności funkcji Eulera możemy wyznaczyć szybko wartość dowolnej liczby naturalnej (funkcja φ jest multiplikatywna, czyli dla nwd(a,b)=1 zachodzi φ(a*b) = φ(a)*φ(b) co od razu daje nam φ(p₁^a₁*p₂^a₂*...*p_k^a_k) = φ(p₁^a₁)*φ(p₂^a₂)*...*φ(p_k^a_k). Przykładowo chcąc wyznaczyć φ(60) widzimy, że 60 = 2²*3*5, więc: φ(60) = φ(2²)φ(3)φ(5) = 2*2*4 = 16 Co do pytania o rozkład liczb na czynniki pierwsze, to na początku sprawdzamy (korzystając z odpowiednich cech podzielności) czy dana liczba dzieli się przez 2,3,5 itd i jeżeli jest przez którąś podzielna, to sprawdzamy tak samo iloraz tej liczby i owej liczby pierwszej, gdy otrzymamy już liczbę która nie dzieli się przez parę początkowych liczb pierwszych to lecimy dalej i sprawdzamy kolejne wyższe liczby pierwsze, ale z reguły to już szybko zlatuje, bo nie musimy sprawdzać wszystkich liczb pierwszych do n, tylko wszystkie dzielniki pierwsze do √n

	2006
Na przykładzie 2006, widzimy, że dzieli się przez 2, więc patrzymy na		= 1003, od
	2

razu widzimy, że 1003 nie dzieli się przez 2,3,5,7,11,13 ale przez 17 już się dzieli i

	1003
otrzymujemy		= 59, co naturalnie jest liczbą pierwszą, więc 2006 = 2*17*59. Czyli
	17

jak ktoś chce policzyć wartość funkcji Eulera dla 2006 to φ(2006) = φ(2)*φ(17)*φ(59) = 1*16*58 = 928. Jak widać znalezienie danego rozkładu jest tutaj bardzo szybkie

Mateusz: Wzór na pewno zapamiętam, a wyszukiwanie przećwiczę. Bardzo dziękuję za pomoc!