Reszty z dzielenia liczb

[PAK]

a)\(\displaystyle{ 2 ^{1000} \mod 77}\)
Próbowałem skorzystać z tw Eulera (z Małego Twierdzenia Fermata chyba nie można bo 77 nie jest pierwsze)

\(\displaystyle{ \phi(77) = 60}\)
\(\displaystyle{ 2 ^{60} = 1 \mod 77}\)
\(\displaystyle{ \left(2 ^{60}\right) ^{6} = 1 \mod 77}\)
\(\displaystyle{ 2 ^{960} = 1 \mod 77}\)

Teraz próbowałem jakoś dobrać te \(\displaystyle{ 2 ^{40}}\) ale cały czas mam wrażenie że wychodzą bardzo duże liczby.

b)\(\displaystyle{ 2 ^{2034} \mod 10}\)
Tutaj nie można zastosować chyba ani MTF (10 nie jest pierwsze) ani tw Eulera ( \(\displaystyle{ NWD(2,10) \neq 1}\))
Próbowałem dobierać potęgi i patrzeć na reszty z dzielenia, ale nie wiele mi to pomogło.

[dec1]

1) \(\displaystyle{ 2^8\equiv 25 \pmod{77}}\), stąd już dość łatwo wyliczyć do czego przystaje \(\displaystyle{ 2^{40}}\)
2) popatrz na ostatnie cyfry, co cztery potęgi się powtarzają

[PAK]

Dobrze myślę że nie zawsze jest tak jak tu, czyli że reszty z dzielenia kolejnych potęg liczby tworzą jakiś okres ?