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}\)?
Liczba elementów odwracalnych, funkcja Eulera
- Janusz Tracz
- Użytkownik
- Posty: 4074
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: Liczba elementów odwracalnych, funkcja Eulera
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}\)
-
- Użytkownik
- Posty: 41
- Rejestracja: 16 paź 2017, o 11:04
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 13 razy
Liczba elementów odwracalnych, funkcja Eulera
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.
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
- Użytkownik
- Posty: 4074
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: Liczba elementów odwracalnych, funkcja Eulera
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)}\)
\(\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)}\)
- Janusz Tracz
- Użytkownik
- Posty: 4074
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: Liczba elementów odwracalnych, funkcja Eulera
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.