Znajdź trzy ostatnie cyfry liczby

[Michalinho]

Najpierw sprawdzasz, czy \(\displaystyle{ (2122, 100)=1}\). Niestety nie, więc robisz tak samo jak z podstawą \(\displaystyle{ 2}\):
\(\displaystyle{ 2122^{482}=100k+r}\), gdzie \(\displaystyle{ r}\) to reszta.
\(\displaystyle{ 2^{482}\cdot 1061^{482}=100k+r}\), stąd \(\displaystyle{ 4|r\Rightarrow r=4r_2}\).
\(\displaystyle{ 2^{480}\cdot 1061^{482}=25k+r_2}\).
Stąd:
\(\displaystyle{ 2^{480}\cdot 1061^{482}\equiv r_2\text{ mod 25}}\).
I teraz oczywiście \(\displaystyle{ (2,25)=1\wedge (1061, 25)=1}\), więc stosujemy twierdzenie Eulera:
\(\displaystyle{ 2^{\phi(25)}\equiv 1\text{ mod 25}\Leftrightarrow 2^{20}\equiv 1\text{ mod 25}}\) i analogicznie \(\displaystyle{ 1061^{20}\equiv 1 \text{ mod 25}}\).
\(\displaystyle{ r_2\equiv 2^{480}\cdot 1061^{482}\equiv 2^{20\cdot 24}\cdot 1061^{20\cdot 24+2}\equiv 1061^2\equiv 11^2\equiv 21\text{ mod 25}}\).
Stąd \(\displaystyle{ r_2=21}\), czyli \(\displaystyle{ r=84}\).
Wolfram potwierdza.