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}}\)