modulo z potęgą

[Kavky]

Witam Was serdecznie!
Mam kłopot ze zrozumieniem jednego z zastosowań MOD. Poniższy przykład przedstawi problematykę:

\(\displaystyle{ \text{MOD} ( 4847 ^{1525} ; 407) = 296}\)
\(\displaystyle{ 1525 = 1024 + 256 + 128 + 64 + 32 + 16 + 4 + 1}\)

\(\displaystyle{ 4847^{1} = 370 \\
4847^{2} = 148 \\
4847^{4} = 333 \\
4847^{8} = 185 \\
4847^{16} = 37 \\
4847^{32} = 148 \\
4847^{64} = 333 \\
4847^{128} = 185 \\
4847^{256} = 37 \\
4847^{512} = 148 \\
4847^{1024} = 333}\)

\(\displaystyle{ 370 \ \ 333 \ \ 37 \ \ 148 \ \ 333 \ \ 185 \ \ 37 \ \ 333}\)

W "magiczny" sposób wyniki łączą się w: \(\displaystyle{ 333 \text{ i }333 = 185; 37 \text{ i } 37 =148; 148, 333 \text{ i }185 = 37}\)
Następuje kolejna faza łącząca w "jakiś" sposób wyniki z linijki wyżej: \(\displaystyle{ 370\ 185\ 37 = 296}\)

Oczywiście nie policzysz na kalkulatorze \(\displaystyle{ 4847^{1024}}\), ale udało mi się dojść do faktu, że wszystkie wyniki są zależne od modulo pierwszej potęgi dzielonej na \(\displaystyle{ 10}\) (w tym przypadku \(\displaystyle{ 37}\)). Problem tkwi, że nie mogę doszukać się jasnego schematu.

Jeśli komuś nie sprawiłoby kłopotów wytłumaczenie co i jak, to prosiłbym o pomoc.

[norwimaj]

Tu chodzi tylko o to, że każdy kolejny wykładnik jest dwa razy większy od poprzedniego, np.
\(\displaystyle{ 4847^8=(4847^4)^2=333^2=185}\).

Można jeszcze zauważyć, że skoro \(\displaystyle{ 4847^{32}=4847^2}\), to dalej to już się będzie cyklicznie powtarzać, więc następnych liczb już nie trzeba liczyć.

Końcowy wynik jest konsekwencją wzoru
\(\displaystyle{ x^{a+b}=x^ax^b}\).

[Kavky]

Dziękuję. Teraz zaczyna mi się to rozjaśniać ^_^

Pozdrawiam!