Funkcja Eulera dla argumentu a przyjmuje wartosć 11424, a=p^2*q^2, przy czym p oraz g są dwiema liczbami pierwszymi róznymi miedzy sobą. Znaleźć liczbę a?
Pomóżcie. dziekuję
Funkcja Eulera - Znaleźć wartość liczby a
Funkcja Eulera - Znaleźć wartość liczby a
tak jak (p,q) = 1 to tez (p^2,q^2) = 1
a wiec mozemy uzyc multyplikatywnej wlasnosci funkcji phi:
phi(p^2*q^2) = phi(p^2) * phi(q^2)
Teraz wiedzac ze dla kazdej liczby pierwszej i naturalnego k mamy phi(p^k) = p^k - p^(k-1) dostajemy:
phi(p^2) * phi(q^2) = (p^2 - p)*(q^2 - q) = p*q*(p-1)*(q-1)
Rozkladamy teraz 11424 na czyniki pierwsze czyli 11424 = 2^5*3*7*17
I rozpatrujemy przypadki kiedy pq*(p-1)*(q-1) = 2^5*3*7*17
Oczywiscie p i q musza byc wystarczajaco duze wystarczy wiec rozpatrzec przypadki dla 3 i 7, i dla 7 i 17
Teraz latwo znalezc ze dla p = 7 i q = 17 dostajemy : 7*17*16*6 = 11424
I tym samym a = (7*17)^2
Jeszce jedna warta uwagi wlasnoscia funkcji phi jest to ze:
phi(n) = n*(1-1/p_1)*(1-1/p_2)*...*(1-1/p_q)
gdzie kazda z liczb p_1, p_2, p_3 ... jest pierwsza i (p_1)*(p_2)*...*(p_n) = n
P.S: Wydaje mi sie ze mozna to rozwiazac bez rozpatrywania przypadkow ale zostawiam to juz tobie...
a wiec mozemy uzyc multyplikatywnej wlasnosci funkcji phi:
phi(p^2*q^2) = phi(p^2) * phi(q^2)
Teraz wiedzac ze dla kazdej liczby pierwszej i naturalnego k mamy phi(p^k) = p^k - p^(k-1) dostajemy:
phi(p^2) * phi(q^2) = (p^2 - p)*(q^2 - q) = p*q*(p-1)*(q-1)
Rozkladamy teraz 11424 na czyniki pierwsze czyli 11424 = 2^5*3*7*17
I rozpatrujemy przypadki kiedy pq*(p-1)*(q-1) = 2^5*3*7*17
Oczywiscie p i q musza byc wystarczajaco duze wystarczy wiec rozpatrzec przypadki dla 3 i 7, i dla 7 i 17
Teraz latwo znalezc ze dla p = 7 i q = 17 dostajemy : 7*17*16*6 = 11424
I tym samym a = (7*17)^2
Jeszce jedna warta uwagi wlasnoscia funkcji phi jest to ze:
phi(n) = n*(1-1/p_1)*(1-1/p_2)*...*(1-1/p_q)
gdzie kazda z liczb p_1, p_2, p_3 ... jest pierwsza i (p_1)*(p_2)*...*(p_n) = n
P.S: Wydaje mi sie ze mozna to rozwiazac bez rozpatrywania przypadkow ale zostawiam to juz tobie...
Funkcja Eulera - Znaleźć wartość liczby a
dziekuje Maks za pomoc, masz racje przypadki nie są potrzebne.