Znajdź resztę z dzielenia...

[Franiut3k]

Witam mam problem z tym zadaniem:
Znajdź resztę z dzielenia \(\displaystyle{ 23^{1000}}\) przez \(\displaystyle{ 61.}\)
Zapisuje i zaczynam liczyć:
\(\displaystyle{ 23^{1000}= \left( 23^{16}\right)^{60} \cdot 23^{40}}\)
\(\displaystyle{ 23^{2}=x\bmod \,61 }\)
\(\displaystyle{ 23^{2}=529\bmod\,61 }\)
\(\displaystyle{ 23^{4}=43\bmod\,61 }\)
\(\displaystyle{ 23^{4}= 43^{2} \bmod\,61 }\)
\(\displaystyle{ 23^{4}= 1849\bmod\,61 }\)
\(\displaystyle{ 23^{4}= 19\bmod\,61 }\)
\(\displaystyle{ 23^{8}= 361\bmod\,61 }\)
itd i dochodzę do
\(\displaystyle{ 23^{128}= 361\bmod\,61 }\) i nie wiem co dalej...
mod - modulo czyli reszta z dzielenia

[Mariusz M]

\(\displaystyle{ 23^{1000}\equiv\left( 23^{60}\right)^{16} \cdot 23^{40}\left( \mod 61\right)\\
23^{1000}\equiv 23^{40}\left( \mod 61\right)\\
529 \equiv 41 \left( \mod 61\right) \\
1681 \equiv 34\left( \mod 61\right) \\
23^5 \equiv 50 \left( \mod 61\right) \\
23^{10}\equiv 60 \left( \mod 61\right)\\
23^{20}\equiv 1 \left( \mod 61\right)\\
23^{40}\equiv 1 \left( \mod 61\right)\\
}\)

[Franiut3k]

Skąd już na początku wiadomo, że
\(\displaystyle{ 23^{1000}\equiv 23^{40}\left( \mod 61\right)\\}\)

[Mariusz M]

Małe twierdzenie Fermata
W zacytowanym wpisie popełniłem błąd w obliczeniach co później wyedytowałem