Reszty z dzielenia dużych liczb

[Boolean]

Witajcie. Chciałbym sobie przypomnieć jak oblicza się reszty z dzielenia dużych liczb przy pomocy małego twierdzenia Fermata, a może innych narzędzi?

Na przykład, jak policzyć
\(\displaystyle{ 7^{13131313}}\) w \(\displaystyle{ \mathbb{Z}_{13}}\) albo \(\displaystyle{ 5^{13579}}\) w \(\displaystyle{ \mathbb{Z}_{11}}\).

Dziękuję i pozdrawiam.

[SaxoN]

MTF mówi nam, że \(\displaystyle{ a^{p-1}\equiv 1\pmod{p}}\), gdzie \(\displaystyle{ p\in\mathbb{P}}\) oraz \(\displaystyle{ a\neq 0}\). Mamy zatem
\(\displaystyle{ 7^{13131313}=7^{1094276\cdot 12 +1}=\big(7^{12}\big)^{1094276}\cdot 7\equiv 1^{1094276}\cdot7\equiv 7 \pmod{13}}\)

\(\displaystyle{ 5^{13579}=5^{1357\cdot 10+9}=\big(5^{10}\big)^{1357}\cdot 5^9\equiv 5^9\pmod{11}}\)

takie \(\displaystyle{ 5^9}\) możemy sprawnie policzyć jako \(\displaystyle{ \big(5^3\big)^3}\) na przykład

[nivwusquorum]

W ogólności do takich obliczeń służy algorytm szybkiego potęgowania modulo, który nie wymaga, aby modulować przez liczbę pierwszą.

... %99gowania

[relax]

Wiem ze odgrzebuje stary temat, ale nie ma sensu robić nowego, mam dokładnie taki sam problem jak autor z tym ze

Co zrobić jeśli duża liczba nie daje nam dokładnej reszty ? tzn \(\displaystyle{ 7^{13131313}}\) w ciełe \(\displaystyle{ \mathbb{F}_13}\), dzielmy przez \(\displaystyle{ 12}\), jak sakson napisał wychodzi \(\displaystyle{ 1094276,083}\).
W notatkach ze studiów, wykładowca zamiast "\(\displaystyle{ 1094276}\)" wpisał "\(\displaystyle{ 1034276}\)" była na to jakaś metoda której nie pamietam.

To samo np w przykładzie \(\displaystyle{ 2^{365789}}\) w ciele \(\displaystyle{ \mathbb{F}_7}\)

\(\displaystyle{ \frac{365789}{6} = 60964,83333}\) ( notatkach mam zamiast tego wydnieje \(\displaystyle{ 60964 + 5}\) - reszta z dzielenia )