Poszukuje dowodu tego że \(\displaystyle{ n|\phi( a^{n}-1)}\) gdzie \(\displaystyle{ \phi}\) jest funkcją tocjent, oraz \(\displaystyle{ a}\) i \(\displaystyle{ n}\) są dowolnymi liczbami naturalnymi.
Ogólnie interesuję mnie miejsce gdzie mogę znaleźć pare ciekawostek dotyczacych tej funkcji. Polecacie jakąś książkę, artykuł?
Dzielnik tocjentu
-
Matiks21
- Użytkownik
- Posty: 562
- Rejestracja: 20 maja 2013, o 16:33
- Płeć: Mężczyzna
- Lokalizacja: Kielce
- Podziękował: 98 razy
Dzielnik tocjentu
Ostatnio zmieniony 8 wrz 2016, o 21:57 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
Powód: Używaj LaTeXa także do pojedynczych symboli.
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Dzielnik tocjentu
Zauważ, że \(\displaystyle{ \NWD(a,a^n-1)=1}\), więc z twierdzenia Eulera otrzymujemy
\(\displaystyle{ a^{\phi(a^n-1)}\equiv 1\pmod{a^n-1}}\)
Z drugiej strony w sposób oczywisty mamy \(\displaystyle{ a^n \equiv 1\pmod{a^n-1}}\).
Zapiszmy \(\displaystyle{ \phi(a^n-1)}\) w postaci \(\displaystyle{ k\cdot n+r}\), gdzie \(\displaystyle{ r \in\left\{ 0,1,\dots n-1\right\}}\). Wówczas \(\displaystyle{ 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
\(\displaystyle{ a^r \equiv 1\pmod{a^n-1}}\), więc skoro \(\displaystyle{ r \in\left\{ 0,1,\dots n-1\right\}}\), to musi być \(\displaystyle{ r=0}\), bo liczby \(\displaystyle{ a^0, a^1 \dots a^{n-1}}\) (dla \(\displaystyle{ a>1}\), przypadek \(\displaystyle{ a=1}\) jest trywialny) są parami różnymi liczbami naturalnymi mniejszymi od \(\displaystyle{ a^n-1.}\)
A co do twierdzeń, to sprawdź w książce Sierpińskiego Teoria liczb (strzelam, tam powinno być wszystko).
\(\displaystyle{ a^{\phi(a^n-1)}\equiv 1\pmod{a^n-1}}\)
Z drugiej strony w sposób oczywisty mamy \(\displaystyle{ a^n \equiv 1\pmod{a^n-1}}\).
Zapiszmy \(\displaystyle{ \phi(a^n-1)}\) w postaci \(\displaystyle{ k\cdot n+r}\), gdzie \(\displaystyle{ r \in\left\{ 0,1,\dots n-1\right\}}\). Wówczas \(\displaystyle{ 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
\(\displaystyle{ a^r \equiv 1\pmod{a^n-1}}\), więc skoro \(\displaystyle{ r \in\left\{ 0,1,\dots n-1\right\}}\), to musi być \(\displaystyle{ r=0}\), bo liczby \(\displaystyle{ a^0, a^1 \dots a^{n-1}}\) (dla \(\displaystyle{ a>1}\), przypadek \(\displaystyle{ a=1}\) jest trywialny) są parami różnymi liczbami naturalnymi mniejszymi od \(\displaystyle{ a^n-1.}\)
A co do twierdzeń, to sprawdź w książce Sierpińskiego Teoria liczb (strzelam, tam powinno być wszystko).