Dwie ostatnie cyfry

[KrolKubaV]

Wyznacz dwie ostatnie cyfry liczby \(\displaystyle{ 17^{17^{17^{17}}} + 18{^{18^{18^{18}}} + 19^{19^{19^{19}}} +20^{20^{20^{20}}}}}\).
Prosiłbym gorąco o jakąś wskazówkę do tego zadania (wiem, że należy obliczyć modulo \(\displaystyle{ 100}\) tej liczby, ale ciągle wychodzą mi ogromne wyniki).

[szw1710]

\(\displaystyle{ 17^{20}}\) daje resztę \(\displaystyle{ 1}\). Poszukaj, jakie potęgi \(\displaystyle{ 18,19,20}\) daję resztę \(\displaystyle{ 1}\). Wyznacz osobno reszty dla każdego ze składników, a potem dla sumy - to już będzie łatwe.

[Premislav]

Jeśli chodzi o \(\displaystyle{ 18}\) i \(\displaystyle{ 20}\), to raczej żadne, gdyż \(\displaystyle{ \NWD(18, 100)>1}\), podobnie \(\displaystyle{ \NWD(20,100)>1}\).
Pierwszą moją myślą w tym zadaniu było twierdzenie Eulera (bo przecież nie będziemy sprawdzać na kartce dwudziestu wykładników, a rozwiązanie z pomocą komputera chyba nie jest tu naszym celem), ale nie wiem, czy autor wątku je zna.
W każdym razie potęgę \(\displaystyle{ 17}\) i potęgę \(\displaystyle{ 19}\) załatwia twierdzenie Eulera, tylko trzeba je „zagnieździć" w wykładnikach, potęga \(\displaystyle{ 20}\) (mamy wszakże parzysty wykładnik) nie ma znaczenia (dlaczego?), najgorzej jest z potęgą \(\displaystyle{ 18}\), nie przychodzi mi do głowy nic lepszego niż rozbicie tego: \(\displaystyle{ 18^2=324\equiv -1\pmod{25}}\), zatem \(\displaystyle{ 18^{4k}\equiv 1 \pmod{25}, \ k=1,2\ldots}\). Ponadto \(\displaystyle{ 18^{l}\equiv 0 \pmod{4}, \ l=2,3\ldots}\), więc po prostym rozważeniu przypadków widzimy, że \(\displaystyle{ 18^{4k}\equiv 76\pmod{100}, \ k=1,2\ldots}\)
Jakbyś miał, KrolKubaV, problem z tym Eulerem do \(\displaystyle{ 17}\) i \(\displaystyle{ 19}\), to pisz, ale może istnieje prostszy sposób.

[KrolKubaV]

Premislav, mógłbyś pokazać jak z tym Eulerem zrobić, bo jak ja robię to i tak na końcu muszę sprawdzić \(\displaystyle{ 17^{17} \mod100}\) i zastanawiam się, czy można to ominąć w jakiś sposób?

[Premislav]

Bardzo mi się nie chciało zabierać do tych obliczeń, ale już trudno, głupio tak zostawiać wątek.

Warto na wstępie coś wiedzieć o funkcji Eulera:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Funkcja_%CF%86

Mamy zatem \(\displaystyle{ \phi(100)=\phi(2^2\cdot 5^2)=\phi(2^2)\cdot \phi(5^2)=2\cdot 20=40}\).
Ponadto, rzecz jasna, \(\displaystyle{ \NWD(17,100)=1}\). A zatem na mocy twierdzenia Eulera mamy \(\displaystyle{ 17^{40}\equiv 1\pmod{100}}\). Po chwili refleksji widzimy, że wobec tego \(\displaystyle{ 17^{40k}\equiv 1\pmod{100}}\) dla \(\displaystyle{ k=1,2,3\ldots}\).
Chcielibyśmy więc przedstawić ten wykładnik \(\displaystyle{ 17}\), czyli \(\displaystyle{ 17^{17^{17}}\) w postaci \(\displaystyle{ 40k+r}\), gdzie konkretnie interesuje nas dokładna wartość \(\displaystyle{ r \in \left\{ 0,1\ldots 39\right\}}\). W tym celu ponownie użyjemy twierdzenia Eulera: mamy
\(\displaystyle{ \NWD(17,40)=1}\) oraz \(\displaystyle{ \phi(40)=\phi(2^3\cdot 5)=\phi(2^3)\phi(5)=4\cdot 4=16}\)
Zatem \(\displaystyle{ 17^{16}\equiv 1\pmod{40}}\) na mocy twierdzenia Eulera i stąd dla dowolnego min NN^+ dostajemy też \(\displaystyle{ 17^{16m}\equiv 1\pmod{40}}\). Ponadto
\(\displaystyle{ 17\equiv 1\pmod{16}}\), zatem łatwo uzyskać, że
\(\displaystyle{ 17^{17}\equiv 1\pmod{16}}\), więc
\(\displaystyle{ 17^{17}=16m+1}\), dla pewnego \(\displaystyle{ m\in \NN^+}\), czyli
\(\displaystyle{ 17^{17^{17}}\equiv 17\pmod{40}}\), a stąd
\(\displaystyle{ 17^{17^{17^{17}}}\equiv 17^{17}\pmod{100}}\).
A tego już nie będę obliczał, bo to jest jakiś syf, ale nie powinno to być bardzo trudne (wczesniej się pomyliłem).

Dla \(\displaystyle{ 19}\) można bardzo podobnie z twierdzenia Eulera, chociaż pewnie szybciej byłoby zauważyć, że \(\displaystyle{ 19^{10}\equiv 1 \pmod{100}}\).-- 4 lis 2017, o 17:49 --A nie, no nie umiem czytać po prostu, doszedłem do tego samego, co Ty.
To faktycznie jest obrzydlistwo. Moim zdaniem nic ładnego z tym nie można zrobić, tylko siłownia pozostaje.
\(\displaystyle{ 17^2\equiv -11 \pmod{100}\\ (17^{2})^8\equiv 11^8 \pmod{100}}\)
Dalej ze wzoru dwumianowego Newtona:
\(\displaystyle{ 11^8=(10+1)^8=\ldots}\)
możemy otrzymać, że \(\displaystyle{ 11^8 \equiv 81\pmod{100}}\)
i w końcu \(\displaystyle{ 17^{17}=17\cdot 17^{16}\equiv 17\cdot 11^8 \pmod{100}}\)
czyli \(\displaystyle{ 17^{17}\equiv 17\cdot 81\pmod{100}}\)
no i z tym już nic ładnego nie zrobisz, ołówek w łapę i pod kreską albo \(\displaystyle{ 81=100-19\equiv -19\pmod{100}}\) i mniejsze rzeczy pod kreską.
Ostatecznie \(\displaystyle{ 17^{17}\equiv 77 \pmod{100}}\)