szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 wrz 2016, o 19:38 
Użytkownik

Posty: 541
Lokalizacja: Kielce
Poszukuje dowodu tego że n|\phi( a^{n}-1) gdzie \phi jest funkcją tocjent, oraz a i n są dowolnymi liczbami naturalnymi.

Ogólnie interesuję mnie miejsce gdzie mogę znaleźć pare ciekawostek dotyczacych tej funkcji. Polecacie jakąś książkę, artykuł?
Góra
Mężczyzna Offline
PostNapisane: 8 wrz 2016, o 21:23 
Użytkownik
Avatar użytkownika

Posty: 13168
Lokalizacja: Wrocław
Zauważ, że \NWD(a,a^n-1)=1, więc z twierdzenia Eulera otrzymujemy
a^{\phi(a^n-1)}\equiv 1\pmod{a^n-1}
Z drugiej strony w sposób oczywisty mamy a^n \equiv 1\pmod{a^n-1}.
Zapiszmy \phi(a^n-1) w postaci k\cdot n+r, gdzie r \in\left\{ 0,1,\dots n-1\right\}. Wówczas a^{\phi(a^n-1)}=a^{kn+r}=(a^n)^k  \cdot a^r\equiv a^r \pmod{a^n-1}. Stąd i z powyższych wniosków dostajemy, że
a^r \equiv 1\pmod{a^n-1}, więc skoro r \in\left\{ 0,1,\dots n-1\right\}, to musi być r=0, bo liczby a^0, a^1 \dots a^{n-1} (dla a>1, przypadek a=1 jest trywialny) są parami różnymi liczbami naturalnymi mniejszymi od a^n-1.



A co do twierdzeń, to sprawdź w książce Sierpińskiego Teoria liczb (strzelam, tam powinno być wszystko).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 NWD - najwiekszy wspólny dzielnik  roin  3
 Największy wspólny dzielnik... - zadanie 2  kordi1221  2
 Największy wspólny dzielnik - zadanie 6  MaxEnergizer  2
 Funkcja tworzaca tocjentu  Matiks21  1
 Relacja równoważności, dzielnik zera  Anonymous  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl