Reszta z dzielenia

[nitka]

Oblicz resztę z dzielenie \(\displaystyle{ 5555^{7777}(mod 191)}\).
Mam już wyznaczoną resztę z dzielenia:
\(\displaystyle{ 5555^{190}\equiv 1(mod 191)}\)
czyli
\(\displaystyle{ 5555^{190*40}\equiv 1^{40}(mod 191)\\
5555^{7600}\equiv 1(mod191)}\)
Ale niestety nie wiem co dalej.
Będę wdzięczna za pomoc.

[bakala12]

Zauważ dodatkowo, że \(\displaystyle{ 5555 \equiv 16 mod 191}\)

[nitka]

To jakoś powinnam przerobić na brakujące mi 5555^177? Nie bardzo wiem jak to wykorzystać.

[robertm19]

\(\displaystyle{ 16^{177}=16^{190-13}=16^{190}(16^{-1})^{13}=12^{13} mod191}\)

[nitka]

Niestety nie bardzo rozumiem skąd pojawia się to \(\displaystyle{ 12^{13}}\)? Bo \(\displaystyle{ 16^{190}\equiv1(mod 191)}\) czyli znika?

[robertm19]

\(\displaystyle{ 16*12=192}\)
Wiec 12 jest elementem odwrotnym.