Liczba elementów odwracalnych, funkcja Eulera

[Scoler]

Jak mogę wyliczyć liczbę elementów odwracalnych w \(\displaystyle{ Z_{30}}\)?
Czy jest to inaczej wyniki funkcji eulera w, którym za argument podaje się w tym wypadku \(\displaystyle{ 30}\)?

[Janusz Tracz]

Z tego co wiem to tak. Odpowiedzią jest \(\displaystyle{ \varphi(30)}\) czyli po policzeniu tego \(\displaystyle{ 30\left( 1- \frac{1}{2} \right) \left( 1- \frac{1}{3} \right)\left( 1- \frac{1}{5} \right)=8}\)

[Scoler]

Dobrze rozumiem, że te liczby w mianownikach to czynniki pierwsze czyli liczby pierwsze, które dzielą 30 bez reszty?

Widzę, że robi się to tak, że dzieli się najpierw 30 przez czynnik pierwszy np. przez 2. Po podzieleniu wychodzi 15. Następnie dzieli się 15 przez kolejny czynnik pierwszy czyli 3 itd.

[Janusz Tracz]

Tak to są czynniki piesze. Ogólnie \(\displaystyle{ \varphi(n)}\) można policzyć na kilka sposobów. Z definicji albo wzorami, są też przypadki szczególne. Ogólnie dla liczby \(\displaystyle{ n}\) która ma czynniki pierwsze \(\displaystyle{ p_1,p_2,...p_k}\) mamy

\(\displaystyle{ \varphi(n)=n\left( 1- \frac{1}{p_1} \right)\left( 1- \frac{1}{p_2} \right) \cdot ... \cdot \left( 1- \frac{1}{p_k} \right)}\)

[Scoler]

Nie rozumiem jak to działa, ale ważne że działa

[Janusz Tracz]

Jakiś element \(\displaystyle{ a}\) zbioru \(\displaystyle{ \ZZ_n}\) ma odwrotny tj \(\displaystyle{ a^{-1}\in\ZZ_n}\) taki że \(\displaystyle{ aa^{-1}=1}\) wtedy i tylko wtedy gdy \(\displaystyle{ \text{NWD}\left( a,n\right)=1}\) czyli są względnie pierwsze. Funkcja \(\displaystyle{ \varphi(n)}\) z definicji zlicza ilość elementów względnie pierwszych z \(\displaystyle{ n}\) nie przekraczających \(\displaystyle{ n}\) więc powie ona i ilości elementów odwracalnych.