Rozszerzony algorytm euklidesa dla przykladu z modulo

[mathemaxh]

Witam,

Mógłby mi ktoś wytłumaczyć jak policzyć za pomocą rozszerzonego algorytmu Euklidesa załóżmy taki przykład:

\(\displaystyle{ 7^{1079} \mod 541 = x}\)

Ps. Policzyć "na piechotę" na komputerze to nie jest problem. Natomiast nie umiem tego w ładny sposób policzyć za pomocą wyżej wymienionego algorytmu. Byłbym wdzięczny gdyby ktoś mi tutaj to wytłumaczył.

[Premislav]

Warto wiedzieć, że liczba \(\displaystyle{ 541}\) jest pierwsza.
Zatem \(\displaystyle{ 7^{540}\equiv 1\pmod{541}}\) na mocy małego twierdzenia Fermata, czyli też
\(\displaystyle{ 7^{1080}=(7^{540})^2\equiv 1^2\pmod{541}}\)
stąd
\(\displaystyle{ 7\cdot 7^{1079}\equiv 1\pmod{541}}\),
a więc trzeba znaleźć odwrotność liczby \(\displaystyle{ 7}\) w \(\displaystyle{ \ZZ_{541}}\).
Mamy
\(\displaystyle{ 541=77 \cdot 7+2\\7=3\cdot 2+1}\),
zatem
\(\displaystyle{ 1=7-3\cdot 2=7-3\cdot (541-77\cdot 7)=-3\cdot 541+232\cdot 7}\),
a więc \(\displaystyle{ 7\cdot 232\equiv 1\pmod{541}}\), czyli w końcu
\(\displaystyle{ 7^{1079}\pmod{541}=232}\)