Twierdzenie Fermata , Eulera i Chińskie Twierdzenie o Reszta

[Akiva]

W jaki sposób obliczyć \(\displaystyle{ 2018 ^{2018}}\) w \(\displaystyle{ \ZZ _{2475}}\). W rozwiązaniu należy wykorzystać Twierdzenie Fermata , Eulera i Chińskie Twierdzenie o Resztach

[Premislav]

Można to zrobić tak:
najpierw zajmiemy się rozkładem liczby \(\displaystyle{ 2475}\) na czynniki pierwsze. Łatwo zauważyć, że
\(\displaystyle{ 2475=2500-25=26\cdot 99=5^2\cdot 3^2 \cdot 11}\).
1) Ponieważ liczba \(\displaystyle{ 2018=2200-182=2200-220+38}\) nie dzieli się przez \(\displaystyle{ 11}\), zatem z małego twierdzenia Fermata mamy \(\displaystyle{ 2018^{10}\equiv 1\pmod{11}}\).
Zatem
\(\displaystyle{ 2018^{2018}=(2018^{10})^{201}\cdot 2018^8\equiv 2018^8\pmod{11}}\)
i tu niestety już trzeba się babrać z liczbami:
\(\displaystyle{ 2018\equiv 5\pmod{11}}\), więc \(\displaystyle{ 2018^3\equiv 125\pmod{11}}\), czyli
\(\displaystyle{ 2018^3\equiv 4\pmod{11}}\) (bo \(\displaystyle{ 125=11^2+4}\)), stąd
\(\displaystyle{ 2018^8\equiv 4\pmod{11}}\).
Ostatecznie zatem \(\displaystyle{ 2018^{2018}\equiv 4\pmod{11}}\).
2)
Oczywiście \(\displaystyle{ 3\nmid 2018}\) (suma cyfr), zatem \(\displaystyle{ \NWD(2018, 9)=1}\), a ponadto wartość funkcji Eulera dla dziewiątki: \(\displaystyle{ \phi(3^2)=(3-1)3^{2-1}=6}\), stąd na mocy twierdzenia Eulera dostajemy
\(\displaystyle{ 2018^6\equiv 1\pmod{9}}\).
Ponadto (dzielimy tutaj z resztą \(\displaystyle{ 2018}\) przez \(\displaystyle{ 6}\))
\(\displaystyle{ 2018^{2018}=\left( 2018^6\right)^{336}\cdot 2018^2\equiv 2018^2\pmod{9}}\)
zaś
\(\displaystyle{ 2018\equiv 2\pmod{9}}\), stąd wreszcie
\(\displaystyle{ 2018^{2018}\equiv 4\pmod{9}}\)

Tutaj drobna uwaga: teraz zauważyłem, że korzystając z: \(\displaystyle{ 2018\equiv 2\pmod{9}}\) można zrobić tę część znacznie prościej, ale nie każdy jest bystry (ja na pewno nie).

3) Oczywiście \(\displaystyle{ \NWD(2018, 25)=1}\) (spójrz na ostatnią cyfrę liczby \(\displaystyle{ 2018}\)), ponadto
\(\displaystyle{ \phi(25)=\phi(5^2)=(5-1)5^{2-1}=20}\), a zatem z twierdzenia Eulera
\(\displaystyle{ 2018^{20}\equiv 1\pmod{25}}\). Stąd
\(\displaystyle{ 2018^{2020}=(2018^{20})^{101}\equiv 1\pmod{25}}\), czyli
\(\displaystyle{ 2018^{2018}\equiv 2018^{-2} \pmod{25}}\)
Ponadto mamy \(\displaystyle{ 2018=25\cdot 80+18\equiv 18\pmod{25}}\)
i element odwrotny do \(\displaystyle{ 18}\) w \(\displaystyle{ \ZZ_{25}}\) można wyznaczyć z rozszerzonego algorytmu Euklidesa:
\(\displaystyle{ 25=1\cdot 18+7\\18=2\cdot 7+4\\7=1\cdot 4+3\\ 4=1\cdot 3+1\\ 1=4-3=(18-2\cdot 7)-(7-4)=\\=18-3\cdot 7+4=18-3\cdot (25-18)+(18-2\cdot 7)=5\cdot 18-3\cdot 25-2\cdot 7=\\=5\cdot 18-3\cdot 25-2\cdot (25-18)=7\cdot 18-5\cdot 25}\)
czyli poszukiwanym elementem odwrotnym do \(\displaystyle{ 18}\) w \(\displaystyle{ \ZZ_{25}}\) jest \(\displaystyle{ 7}\).
Zatem w \(\displaystyle{ \ZZ_{25}}\) mamy \(\displaystyle{ 2018^{-2}=7^2=49\equiv 24}\), czyli mamy
\(\displaystyle{ 2018^{2018}\equiv 24\pmod{25}}\)

Łączymy teraz 1), 2), 3) i korzystamy z chińskiego twierdzenia o resztach.
Układ kongruencji:
\(\displaystyle{ \begin{cases} x\equiv 4\pmod{11}\\ x\equiv 4 \pmod{9}\\ x\equiv 24\pmod{25} \end{cases}}\)
ma jedyne rozwiązanie w \(\displaystyle{ \ZZ_{2475}}\) i weźmy sobie jakiś ulubiony algorytm pozwalający na znalezienie tego rozwiązania. Jakiś w miarę ładny (też tam się przewija rozszerzony algorytm Euklidesa) jest chyba opisany na wiki w artykule o CRT, a jak się zdaje też na wazniaku. Tam jest bodajże taki: mamy \(\displaystyle{ 2475=11\cdot 25\cdot 9}\) (oczywiście te czynniki są parami względnie pierwsze, co należy do założeń chińskiego twierdzenia o resztach) i teraz znajdźmy z użyciem rozszerzonego algorytmu Euklidesa takie całkowite
\(\displaystyle{ s_1, \ t_1, \\s_2, \ t_2,\\ s_3, \ t_3}\),
że
\(\displaystyle{ s_1\cdot \frac{2475}{11} +t_1\cdot 11=1}\) i tak dalej (nie chce mi się pisać).
Mamy:
\(\displaystyle{ \frac{2475}{11}=225\\ 225=20\cdot 11+5\\11=2\cdot 5+1\\ 1=11-2\cdot 5=11-2\cdot (225-20\cdot 11)=41\cdot 11-2\cdot 225}\),
czyli \(\displaystyle{ s_1=-2, \ t_1=11}\).
Zauważmy też, że liczba \(\displaystyle{ -2\cdot 225}\) spełnia następujące warunki:
daje resztę \(\displaystyle{ 1}\) z dzielenia przez \(\displaystyle{ 11}\) oraz daje resztę \(\displaystyle{ 0}\) z dzielenia tak przez \(\displaystyle{ 25}\), jak i przez \(\displaystyle{ 9}\).
Zapamiętujemy tę liczbę \(\displaystyle{ -2\cdot 225}\), przyda się.

Teraz tak: \(\displaystyle{ \frac{2475}{25}=99}\) i wykonujemy rozszerzony algorytm Euklidesa dla
\(\displaystyle{ 99}\) i \(\displaystyle{ 25}\) (oczywiście \(\displaystyle{ \NWD(25,99)=1}\)):
\(\displaystyle{ 99=3\cdot 25+24\\25=1\cdot 24+1\\1=25-24=25-(99-3\cdot 25)=-99+4\cdot 25}\),
zatem \(\displaystyle{ s_2=-1, \ t_2=4}\). Ponadto przyda nam się jeszcze liczba \(\displaystyle{ -99}\), która spełnia oczywiście z uwagi na powyższe:\(\displaystyle{ -99\equiv 1\pmod{25}}\), a także \(\displaystyle{ 9| -99, \ 11| -99}\).

Wreszcie: \(\displaystyle{ \frac{2475}{9}=11\cdot 25=275}\) i wykonujemy rozszerzony algorytm Euklidesa dla \(\displaystyle{ 275}\) i \(\displaystyle{ 9}\):
\(\displaystyle{ 275=30\cdot 9+5\\9=1\cdot 5+4\\5=1\cdot 4+1\\ 1=5-4=5-(9-5)=\\=2\cdot 5-9=2\cdot (275-30\cdot 9)-9=-61\cdot 9+2\cdot 275}\),
czyli \(\displaystyle{ s_3=2, \ t_3=-61}\)
i tutaj istotna będzie liczba \(\displaystyle{ 2\cdot 275}\)

W końcu: reszta z dzielenia liczby \(\displaystyle{ (-2\cdot 225)\cdot {\red 4}+(-1\cdot 99)\cdot {\blue 24}+2\cdot 275\cdot {\green 4}}\) przez \(\displaystyle{ 2475}\) jest szukanym jedynym rozwiązaniem wyjściowej kongruencji w \(\displaystyle{ \ZZ_{2475}}\).
Na czerwono reszta z dzielenia \(\displaystyle{ 2018^{2018}}\) przez \(\displaystyle{ 11}\), na niebiesko reszta z dzielenia \(\displaystyle{ 2018^{2018}}\) przez \(\displaystyle{ 25}\), na zielono reszta z dzielenia \(\displaystyle{ 2018^{2018}}\) przez \(\displaystyle{ 9}\).
Na kalkulatorze napieprzamy, że
\(\displaystyle{ (-2\cdot 225)\cdot {\red 4}+(-1\cdot 99)\cdot {\blue 24}+2\cdot 275\cdot {\green 4}=-1976}\), a reszta z dzielenia tej ostatniej liczby, równej \(\displaystyle{ -2475+499}\), przez \(\displaystyle{ 2475}\) wynosi \(\displaystyle{ 499}\).
Zatem odpowiedź wygląda tak:
\(\displaystyle{ 2018^{2018}\equiv 499\pmod{2475}}\)