Wyliczyć modulo stosując podstawowe własności

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
strefa61
Użytkownik
Użytkownik
Posty: 185
Rejestracja: 12 gru 2013, o 22:22
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 77 razy

Wyliczyć modulo stosując podstawowe własności

Post autor: strefa61 »

Cześć, mam zadanie, w którym muszę policzyć:
\(\displaystyle{ 19^{19^{19}} \pmod{16}}\)
Zauważmy, ze: \(\displaystyle{ 3^4 \equiv -1\pmod{16}}\)
\(\displaystyle{ 19 \equiv -1 \pmod{4} \Rightarrow 19^{19} \equiv -1 \pmod {4} \Rightarrow 19^{19} = 4k+3, \ k\in \mathbbb{Z}{}\)
Zatem:
\(\displaystyle{ 19^{19^{19}} = 19^{4k + 3}}\)
Zauważam, że: \(\displaystyle{ 3^3 \equiv 11\pmod{16}}\) zatem:
\(\displaystyle{ 19 \equiv 3 \pmod {16} \Rightarrow 19^{19^{19}} \equiv 3^{19^{19}} \pmod{16}}\)
\(\displaystyle{ 3^{19^{19}} = 3^{4k} \cdot 3^3 \Rightarrow 3^{19^{19}} \equiv (-1)^{k} \cdot 11 \pmod {16} \equiv 19^{19^{19}} \pmod{16}}\)
Zatem pozostaje rozwiązać czy k jest parzyste czy nieparzyste. Żeby to zrobić sprawdzam:
\(\displaystyle{ 19^{19} \pmod{8}}\)
\(\displaystyle{ 19\equiv 3 \pmod{8} \Rightarrow 19^2\equiv 9 \pmod{8} \Rightarrow 19^2 \equiv 1 \pmod{8}}\)
\(\displaystyle{ (19^2)^8 \equiv 1 \pmod{8} \Rightarrow 19^{19} \equiv 3 \pmod{8}}\)
Zatem \(\displaystyle{ 19^{19}=4k+3=4\cdot 2t + 3}\) czyli k jest parzyste. Wracając do równania:
\(\displaystyle{ (-1)^{4k}\cdot 11 \equiv 19^{19^{19}} \pmod{16} \equiv 11 \pmod{16}}\)
Moje pytania: czy to rozwiązanie jest ok i czy stosując te najbardziej podstawe własności działań modulo widzi ktoś tutaj jakieś prostsze rozwiązania?
Ostatnio zmieniony 9 mar 2019, o 16:51 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Majeskas
Użytkownik
Użytkownik
Posty: 1456
Rejestracja: 14 gru 2007, o 14:36
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 49 razy
Pomógł: 198 razy

Wyliczyć modulo stosując podstawowe własności

Post autor: Majeskas »

Ja bym zrobił tak:
\(\displaystyle{ 19 \equiv 3 \pmod{16}}\), więc \(\displaystyle{ 19^{19} \equiv 3^{19} \pmod{16}}\)

\(\displaystyle{ 3^{19}=\left( 3^4\right)^4\cdot3^3\equiv1^4\cdot27\equiv11\pmod{16}}\)

Stąd \(\displaystyle{ 19^{19}=16k+11}\)

\(\displaystyle{ 19^{19^{19}}\equiv3^{19^{19}}=3^{16k+11}=\left( 3^4\right)^{4k}\cdot3^{11}\equiv3^{11}=\left( 3^4\right)^2\cdot3^3\equiv27\equiv11 \pmod{16}}\)
ODPOWIEDZ