kongruencja i NWD

[Kivi_ninja]

Witam, mam problem z rozwiązaniem przykładowych równań metodą, którą miałem przedstawioną na wykładzie - niestety wykładowca niezbyt poprawnie włada po polsku i nie byłem w stanie zrozumieć treści tych wykładów - byłbym ogromnie wdzięczny za pomoc w wyjaśnieniu tej metody.

Przykład:
\(\displaystyle{ 8x \equiv 4 \pmod{13}}\)

W moich notatkach jest zapisane, że należy zrobić to w 2 krokach:
\(\displaystyle{ 1. \ m\cdot s \equiv_n 1}\)

\(\displaystyle{ 2. \ x = sa \ MOD \ n}\)

Co do pierwszego punktu mam jeszcze wzmiankę, że jest to algorytm Euklidesa i rysujemy dla niego odpowiednią tabelkę:

\(\displaystyle{ NWD(8,13) = 1}\)

\(\displaystyle{ \begin{vmatrix}
a & q & s & t \\
98 & & 1 & 0\\
13 & 7 & 0 & 1\\
7 & 1 & 1 & -7\\
6 & 1 & -1 & 8\\
1 & 6 & 2 & -15
\end{vmatrix}}\)

\(\displaystyle{ 1 = s8 + t13 \\
1 = s8 \mod \ 13 \\
4 = 4s8 \\
4s\mod\ 13 = x}\)

Nie rozumiem skąd się bierze \(\displaystyle{ s}\) i \(\displaystyle{ t}\) w tej tabelce, po co to w ogóle wyliczamy i jak rozwiązuje się końcowe równanie.

[Medea 2]

Możesz rozwiązać to konkretne zadanie szybciej: podziel przez cztery obie strony (bo \(\displaystyle{ (4,13) = 1}\)) i zauważ, że siedem jest rozwiązaniem \(\displaystyle{ 2x = 1}\) (modulo \(\displaystyle{ 13}\)).

[Kivi_ninja]

Bardzo dziękuję za pomoc, ale zależy mi na zrozumieniu metody prezentowanej powyżej.

[Medea 2]

Ogólna metoda działa tak właśnie. Pokażę Ci to na prostym przykładzie, w sieci znajdziesz więcej materiałów.

Powiedzmy, że chcesz rozwiązać równanie \(\displaystyle{ 17x = 5 \pmod {132}}\). Nie za bardzo wiadomo, jakie to rozwiązanie jest. W takim razie zaczynasz od pomocniczego: \(\displaystyle{ 17x = 1 \pmod {132}}\). Zamieniasz je na jeszcze prostsze, \(\displaystyle{ 17x + 132y = 1}\), gdzie \(\displaystyle{ x,y}\) są całkowite. Tu przydaje się rozszerzony algorytm Euklidesa.

\(\displaystyle{ 132 = 7 \cdot 17 + 13}\)
\(\displaystyle{ 17 = 1 \cdot 13 + 4}\)
\(\displaystyle{ 13 = 3 \cdot 4 + 1}\)

Zatem:

\(\displaystyle{ 1 = 13 - 3 \cdot 4}\)
\(\displaystyle{ 1 = 13 - 3 \cdot (17 - 1 \cdot 13) = 4 \cdot 13 - 3 \cdot 17}\)
\(\displaystyle{ 1 = 4 \cdot (132 - 7 \cdot 17) - 3 \cdot 17 = 4 \cdot 132 -31 \cdot 17}\)

Mamy rozwiązanie prostszego równania: \(\displaystyle{ x = -31}\), \(\displaystyle{ y = 4}\). W takim razie \(\displaystyle{ -31 \equiv 101}\) jest rozwiązaniem pomocniczego, a \(\displaystyle{ 505 \equiv 109 \pmod {132}}\): wyjściowego

[Kivi_ninja]

O! Bardzo dziękuję za pomoc ten przykład rzeczywiście wiele wyjaśnia.

Zastanawiam się jeszcze po co rysować tę tabelkę (chodzi mi dokładnie o element s i t)?
Jest ona rysowana do każdego zadania jakie przedstawiał nam wykładowca.