Reszta z dzielenia

[Kinga_O]

Muszę obliczyć

\(\displaystyle{ 161^{321} \mod 79}\)

Wiem, że to będzie tyle samo co

\(\displaystyle{ 161^{9} \mod 79}\)

ale dalej nie wiem, jak to szybko policzyć, proszę o pomoc.

[Premislav]

Zauważ, że \(\displaystyle{ 161 \equiv 3 \pmod{79}}\), toteż
\(\displaystyle{ 161^9 \equiv 3^9 \pmod{79}}\)
a to już nie jest takie złe, gdyż
\(\displaystyle{ 3^4 \equiv 2 \pmod{79}\\(3^4)^2 \equiv 2^2 \pmod{79}\dots}\)

[PoweredDragon]

Zauważ, że \(\displaystyle{ 161^{78} \equiv 161^{308} \equiv 1 \pmod {79}}\)

[Premislav]

PoweredDragon, sorry, ale napisałeś coś kompletnie nieprawdziwego.
Ani nie jest prawdą, że \(\displaystyle{ 161^{78}\equiv 161^{308} \pmod{79}}\), ani nie zachodzi
\(\displaystyle{ 161^{308} \equiv 1 \pmod {79}}\).
Natomiast prawdą oczywiście jest, że
\(\displaystyle{ 161^{78}\equiv 1\pmod{79}}\) (choćby z małego twierdzenia Fermata). Co więcej, widać, że
Kinga_O z tego skorzystała.