Liczby pierwsze i funkcja Euler'a
-
olgalagowska
- Użytkownik
- Posty: 88
- Rejestracja: 28 paź 2010, o 13:05
- Płeć: Kobieta
- Podziękował: 8 razy
Liczby pierwsze i funkcja Euler'a
Pokaz, ze jesli \(\displaystyle{ p}\) jest liczba pierwsza i \(\displaystyle{ m}\) jest liczba calkowita dodatnia, wtedy liczba calkowita \(\displaystyle{ x}\) w przedziale \(\displaystyle{ 1 \le x \le p^m}\) nie jest wzglednie pierwsza do \(\displaystyle{ p^m}\) tylko i wylacznie jesli jest wielokrotnoscia \(\displaystyle{ p}\). Wydedukuje, ze \(\displaystyle{ \Phi (p^m)=p^m-p^{m-1}}\)
-
Adifek
- Użytkownik
- Posty: 1567
- Rejestracja: 15 gru 2008, o 16:38
- Płeć: Mężczyzna
- Lokalizacja: Ostrzeszów/Wrocław
- Podziękował: 8 razy
- Pomógł: 398 razy
Liczby pierwsze i funkcja Euler'a
\(\displaystyle{ \Leftarrow}\)
Jeśli \(\displaystyle{ x=np}\), to oczywiste, bo \(\displaystyle{ p^{m}}\) oraz \(\displaystyle{ x}\) dzielą się przez \(\displaystyle{ p}\), więc nie są względnie pierwsze.
\(\displaystyle{ \Rightarrow}\)
Niech \(\displaystyle{ x}\) oraz \(\displaystyle{ p^{m}}\) nie będą względnie pierwsze. Istnieje więc taka liczba pierwsza, że występuje w rozkładach an czynniki pierwsze obu tych liczb. Ale jedyną liczbą pierwszą dzielącą \(\displaystyle{ p^{m}}\) jest \(\displaystyle{ p}\). Stąd tą liczba musi być \(\displaystyle{ p}\). Zatem \(\displaystyle{ x}\) dzieli się przez \(\displaystyle{ p}\) (bo występuje ona w jego rozkładzie na czynniki pierwsze), a stąd \(\displaystyle{ x=np}\) dla pewnego \(\displaystyle{ n}\) naturalnego dodatniego.
Jeśli \(\displaystyle{ x=np}\), to oczywiste, bo \(\displaystyle{ p^{m}}\) oraz \(\displaystyle{ x}\) dzielą się przez \(\displaystyle{ p}\), więc nie są względnie pierwsze.
\(\displaystyle{ \Rightarrow}\)
Niech \(\displaystyle{ x}\) oraz \(\displaystyle{ p^{m}}\) nie będą względnie pierwsze. Istnieje więc taka liczba pierwsza, że występuje w rozkładach an czynniki pierwsze obu tych liczb. Ale jedyną liczbą pierwszą dzielącą \(\displaystyle{ p^{m}}\) jest \(\displaystyle{ p}\). Stąd tą liczba musi być \(\displaystyle{ p}\). Zatem \(\displaystyle{ x}\) dzieli się przez \(\displaystyle{ p}\) (bo występuje ona w jego rozkładzie na czynniki pierwsze), a stąd \(\displaystyle{ x=np}\) dla pewnego \(\displaystyle{ n}\) naturalnego dodatniego.