Wyznaczanie reszt z dzielenia.

[ITman]

Umiem wyznaczyć resztę przy pomocy małego twierdzenia Fermata.
np. \(\displaystyle{ 39^{100} \mod}\) \(\displaystyle{ 13}\)
\(\displaystyle{ a^{p-1} = 1}\)
\(\displaystyle{ 39^{13-1} = 1}\)
\(\displaystyle{ 39^{12}=1}\)
\(\displaystyle{ 39^{8 \cdot 12}=1}\)
\(\displaystyle{ 39^{100}=1 \cdot 39^4}\)
\(\displaystyle{ 39^{4}\mod}\) \(\displaystyle{ 13}\)
Ale co zrobić ,gdy liczba przez którą dziele nie jest pierwsza.
np. \(\displaystyle{ 39^{100}\mod}\) \(\displaystyle{ 38}\)

[Kaf]

W tym przypadku można zauważyć, że \(\displaystyle{ 39 \equiv 1 \pmod{38}}\), ale na ogół trzeba zastosować twierdzenie Eulera.

[bakala12]

Źle. Małe twierdzenie Fermata nie działa. \(\displaystyle{ NWD\left( 13,39\right)=13}\)

[Valiors]

Zauważamy, że:
\(\displaystyle{ 39 \equiv 1 \pmod{38}}\)
Kongruencje można potęgować obustronnie, więc korzystamy z tego faktu, podnosząc obie strony do potęgi 100.
\(\displaystyle{ 39^{100} \equiv 1^{100} \pmod{38}}\)
\(\displaystyle{ 39^{100} \equiv 1 \pmod{38}}\)
\(\displaystyle{ 1 < 38}\) więc liczba \(\displaystyle{ 1}\) to reszta z dzielenia \(\displaystyle{ 39^{100}}\) przez \(\displaystyle{ 38}\).