Dwie ostatnie cyfry liczby

[Hatcher]

Zad.
Znaleźć dwie ostatnie cyfry liczby: \(\displaystyle{ 9^{99}}\).

\(\displaystyle{ 9^3 \equiv 29\pmod{100}}\)
\(\displaystyle{ 9^9 \equiv 29^3 \pmod{100}, 29^3 \equiv 89 \pmod{100} \Rightarrow 9^9 \equiv 89 \pmod{100}}\)
\(\displaystyle{ 89 \equiv -11 \pmod{100}}\)
\(\displaystyle{ 9^9 \equiv -11 \pmod{100}}\)
\(\displaystyle{ 9^{45} \equiv (-11)^5 \pmod{100}}\)
\(\displaystyle{ 9^{45} \equiv -51 \pmod{100}}\)
\(\displaystyle{ 9^{45} \equiv 49 \pmod{100}}\)
\(\displaystyle{ 9^{90} \equiv 49^2 \pmod{100}}\)
\(\displaystyle{ 9^{90} \equiv 1 \pmod{100}}\)

\(\displaystyle{ 9^{90} \cdot 9^9=9^{99} \equiv 89 \cdot 1 \pmod{100} \equiv 89 \pmod{100}}\)

Czy mój sposób rozwiązania jest dobry?
Bardzo proszę o sprawdzenie.

[BettyBoo]

Wynik masz poprawny, ale nie bardzo rozumiem, na czym właściwie polega ten sposób - wygląda to raczej dość przypadkowo.

Najłatwiej to chyba obliczyć, korzystając najpierw z tw Eulera - ponieważ 9 i 100 są względnie pierwsze, to \(\displaystyle{ 9^{\varphi(100)}\equiv 1\ (mod \ 100)}\), gdzie \(\displaystyle{ \varphi(100)=100\cdot \frac{1}{2}\cdot \frac{4}{5}=40}\). Mamy więc \(\displaystyle{ 9^{99}\equiv 9^{19}\ (mod\ 100)}\).

Aby najszybciej obliczyć ta potęgę, rozkładasz ją na sumę potęg dwójki: 19=16+2+1. Obliczasz po kolei \(\displaystyle{ 9^2, 9^4=(9^2)^2, 9^8=(9^4)^2, 9^{16}=(9^8)^2}\), a potem bierzesz te potęgi, które Ci są potrzebne.

Jeśli nie znasz tw Eulera, to rozpisujesz oryginalną potęgę na sumę potęg dwójki i liczysz j.w.

Pozdrawiam.

[gendion]

jak dla mnie sposób przedstawiony przez Hatcher, jest jak najbardziej poprawny.

IMO nic nie jest przypadkowo, wszystko ładnie rozpisane po kolei.