Obliczyć wartości tych wyrażeń modulo

[ReallyGrid]

Powiedzcie mi jak się oblicza wyrażenia jak poniżej. Mam do obliczenia 3 takie wyrażenia:

\(\displaystyle{ 1284^{2017}\ (\text{mod}\ 64) \qquad 628^{3517}\ (\text{mod}\ 19) \qquad 8285^{8005}\ (\text{mod}\ 82)}\)

Chodzi mi o schemat algorytmu rozwiązania tego

[Premislav]

Drugi i trzeci przykład idą z twierdzenia Eulera. Twierdzenie Eulera mówi nam, że jeśli
\(\displaystyle{ a,b \in \NN^+}\) i \(\displaystyle{ (a,b)=1}\), to \(\displaystyle{ a^{\varphi(b)}\equiv 1\pmod{b}}\), gdzie \(\displaystyle{ \varphi}\) to

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Funkcja_%CF%86

.
W szczególności gdy \(\displaystyle{ b}\) jest pierwsze, to \(\displaystyle{ \varphi(b)=b-1}\) i mamy małe twierdzenie Fermata.

Czasami jednak można uzyskać wynik szybciej (ale raczej nie da się tego sformułować w postaci algorytmu, co do algorytmu to j.w. twierdzenie Eulera):
\(\displaystyle{ 628=570+57+1\equiv 1\pmod{19}}\), więc i \(\displaystyle{ 628^{3517}\equiv 1\pmod{19}}\).
\(\displaystyle{ 8285=8282+3\equiv 3\pmod{82}}\), więc \(\displaystyle{ 8285^{8005}\equiv 3^{8005}\pmod{82}}\). Teraz zauważmy, że \(\displaystyle{ 3^4=81\equiv -1\pmod{82}}\), toteż \(\displaystyle{ \left( 3^4\right)^{2001}\equiv (-1)^{2001}\pmod{82}}\), czyli \(\displaystyle{ 3^{8005}\equiv -3\pmod{82}}\), a jak kto woli, \(\displaystyle{ 3^{8005}\equiv 79\pmod{82}}\).

-- 16 sty 2018, o 00:57 --

Natomiast w takich zadaniach, jak ten pierwszy przykład (wszak \(\displaystyle{ (1284,64)>1}\), bo np. \(\displaystyle{ 4}\) dzieli obie te liczby) nie znam żadnej ogólnej metody. Tutaj widać, że \(\displaystyle{ 4| 1284}\), więc
\(\displaystyle{ 4^{2017} |1284^{2017}}\), a więc tym bardziej \(\displaystyle{ 4^3|1284^{2017}}\), a przecież \(\displaystyle{ 4^3=64}\), czyli
\(\displaystyle{ 64|1284^{2017}}\), tj. \(\displaystyle{ 1284^{2017}\equiv 0\pmod{64}}\).