Wyznacz dwie ostatnie cyfry liczby.Kongruencja

[xxDorianxx]

Witam uczę się właśnie kongruencji i mam problem z tymi przykładami.

Wyznacz dwie ostatnie cyfry liczby.

a) \(\displaystyle{ 6 ^{10}}\)
b) \(\displaystyle{ 13^{13}}\)
Jeśli nie obejdzie się bez Funkcja Carmichaela czy też Funkcji Eulera to jak byście mogli pokazać użycie ich na właśnie tych przykładach.-- 1 lip 2018, o 21:58 --dodam że potrafię to zrobić bez kongruencji ale chcą ją dobrze przećwiczyć.

[Premislav]

Szczęść Boże.

a)
\(\displaystyle{ 6^4=1296\equiv -4\pmod{100}\\ (6^4)^2\equiv 16\pmod{100}\\ 6^{10}=(6^4)^2\cdot 6^2\equiv 16\cdot 36\pmod{100}}\)
czyli w końcu \(\displaystyle{ 6^{10}\equiv 76\pmod{100}}\),
stąd te dwie ostatnie cyfry wyglądają tak: \(\displaystyle{ 76}\).

b)
\(\displaystyle{ 13\equiv 1\pmod{4}}\), toteż \(\displaystyle{ 13^{13}\equiv 1\pmod{4}}\).
Ponadto łatwo obliczyć w pamięci, że \(\displaystyle{ 13^6\equiv 9\pmod{25}}\), a więc \(\displaystyle{ 13^{12}=(13^6)^2\equiv 6\pmod{25}}\) oraz
\(\displaystyle{ 13^{13}=(13^6)^2\cdot 13\equiv 3\pmod{25}}\).
Zatem liczba \(\displaystyle{ 13^{13}\pmod{100}}\)
jest rozwiązaniem układu kongruencji:
\(\displaystyle{ \begin{cases} x\equiv 1\pmod{4}\\ x\equiv 3\pmod{25} \end{cases}}\)
Z chińskiego twierdzenia o resztach ten układ ma jedyne rozwiązanie w \(\displaystyle{ \ZZ_{100}}\) i jak nam się nie chce używać tego algorytmu powiązanego z rozszerzonym algorytmem Euklidesa, to można zgadnąć rozwiązanie: \(\displaystyle{ x\equiv 53\pmod{100}}\).
Stąd te dwie ostatnie cyfry liczby \(\displaystyle{ 13^{13}}\) wyglądają tak: \(\displaystyle{ 53}\).

Z Bogiem, KW

[xxDorianxx]

Dzięki wielkie po raz kolejny 8)