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}}\).