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?
Wyliczyć modulo stosując podstawowe własności
-
- 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
Ostatnio zmieniony 9 mar 2019, o 16:51 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
-
- 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
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}}\)
\(\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}}\)