Wyznacz dwie ostatnie cyfry

[studciak123]

Wyznacz dwie ostatnie cyfry w rozwinięciu dziesiętnym liczby \(\displaystyle{ 76^{76}}\) .
Próbowałem to robić przez układ kongurencji tzn. znaleźć potęgę, dla której \(\displaystyle{ 76^{x} \equiv 1 \bmod 100}\) i rozpisaniu przy jej pomocy \(\displaystyle{ 76^{76}}\) , jednak zauważam, że \(\displaystyle{ 76^{x} \equiv 76 \bmod 100}\) i tu mam problem, bo nie wiem jak to pokazać, że to jest rzeczywiście \(\displaystyle{ 76}\) .

[Premislav]

Mamy \(\displaystyle{ 100=4\cdot 25}\) i \(\displaystyle{ \NWD(4,25)=1}\) . Oczywiście \(\displaystyle{ 76\equiv 0\pmod{4}}\) , stad i \(\displaystyle{ 76^{76}\equiv 0\pmod{4}}\) , a ponadto \(\displaystyle{ 76\equiv 1\pmod{25}}\) , toteż \(\displaystyle{ 76^{76}\equiv 1\pmod{25}}\) .
Zatem dwie ostatnie cyfry liczby \(\displaystyle{ 76^{76}}\) muszą tworzyć liczbę podzielną przez \(\displaystyle{ 4}\) (cecha podzielności przez \(\displaystyle{ 4}\) ) i zarazem tak utworzona liczba musi być postaci \(\displaystyle{ 25k+1}\) dla jakiegoś \(\displaystyle{ k \in\left\{ 0,1,2,3\right\}}\) . Bezpośrednie sprawdzenie pokazuje, że liczby \(\displaystyle{ 1,\:26,\:51}\) odpadają i jedyna możliwość to \(\displaystyle{ 76=3\cdot 25+1}\), więc istotnie
\(\displaystyle{ 76^{76}\equiv 76\pmod{100}}\) .
Tak naprawdę istotnie łatwo to uogólnić na \(\displaystyle{ 76^{n}\equiv 76\pmod{100}}\) dla dowolnego \(\displaystyle{ n\in \NN^+}\) i robi się to tak samo. Może da się ładniej, ale ja jestem głupi.

[Janusz Tracz]

Można by \(\displaystyle{ 76^{n} \equiv 76 \bmod 100}\) udowodnić indukcyjnie.

\(\displaystyle{ \mathbf{1.}\ \ \ 76 \equiv 76 \bmod 100}\)

załóżmy więc że dla pewnego \(\displaystyle{ n\in\NN}\) zachodzi \(\displaystyle{ 76^{n} \equiv 76 \bmod 100}\) i sprawdźmy czy dla \(\displaystyle{ n+1}\) też zachodzi.

\(\displaystyle{ \mathbf{2.}\ \ \ 76^{n+1} \bmod 100=\left( \left( 76^{n}\bmod 100\right) \cdot \left( 76\bmod 100\right) \right)\bmod 100= 76^2\bmod 100}\)

co kończy dowód bo \(\displaystyle{ 76^2=5776}\).