kongruencja i dwie ostatnie cyfry

[kuba746]

Mój problem dotyczy tego jak policzyć dwie ostatnie cyfry liczby \(\displaystyle{ 9^{(9^9)}}\)

[Artist]

Najpierw zauważmy, że:
\(\displaystyle{ \varphi(100)=40}\)
\(\displaystyle{ NWD_{(9,100)}=1}\)
\(\displaystyle{ 9^{9}=(9^{2})^{4}\cdot 9 \equiv 1^{4} \cdot 9=9 \ (mod \ 40)}\)

\(\displaystyle{ 9^{(9^{9})} \equiv 9^{9} \equiv 89 \ (mod \ 100)}\)

[kuba746]

a jeszcze co oznacza \(\displaystyle{ \varphi(100)=40}\)??

[tomalla]

Jest to funkcja Eulera. Oznacza to tyle, że jest 40 liczb względnie pierwszych ze 100, jednocześnie mniejszych od 100. Można to obliczyć w ten sposób:

\(\displaystyle{ \varphi(100)=\varphi(25\cdot4)=\varphi(25)\cdot\varphi(4)=20\cdot 2=40}\)

[Artist]

Jest to funkcja Eulera. Oznacza to tyle, że jest 40 liczb względnie pierwszych ze 100, jednocześnie mniejszych od 100. Można to obliczyć w ten sposób:

\(\displaystyle{ \varphi(100)=\varphi(25\cdot4)=\varphi(25)\cdot\varphi(4)=20\cdot 2=40}\)

Albo:
\(\displaystyle{ 100=2^{2} \cdot 5^{2} \Rightarrow \varphi=100(1-\frac{1}{2})\cdot(1-\frac{1}{5})=40}\)

[kuba746]

Artist, już sobie spr. jak policzyć funkcję Eulera
a jak byłoby w ogólnym przypadku \(\displaystyle{ a^{(x^y)}}\)??

[Artist]

To zależy czy np. \(\displaystyle{ NWD_{(a,100)}=1}\)

jeśli tak to:
\(\displaystyle{ a^{40} \equiv 1 \ (mod \ 100)}\)
Zapisujesz teraz \(\displaystyle{ x^{y}\equiv z \ (mod \ 40)}\)
Reasumując:

\(\displaystyle{ a^{(x^{y})(mod40)}(mod100)}\)

Nic więcej chyba nie da się uzyskać.

PS.
Poczytaj jeszcze o funkcji Carmichaela.

Z niej masz już, ze:
\(\displaystyle{ a^{20} \equiv 1 (mod \ 100)}\)