Rozwiąż równanie kongruencyjne

[netsprint]

Rozwiąż równanie kongruencyjne: \(\displaystyle{ 17x \equiv 13(mod 19)}\)


stąd wyliczyłem: \(\displaystyle{ NWD(19,17)=1}\)


i teraz z na podstawie roszerzonego algorytmu euklidesa wyszło:
\(\displaystyle{ 1=17-8 \cdot 2=17(8 \cdot (19-17))=-8 \cdot 19+9 \cdot 17}\)



\(\displaystyle{ 1=-8 \cdot 19+9 \cdot 17 \\
1+8 \cdot 19=9 \cdot 17}\)

Dochodzę do czegoś takiego i jak mam dalej z tego obliczyć element odwrotny do 17?

[brzoskwinka1]

Czyli \(\displaystyle{ 17^{-1} = 9}\) w \(\displaystyle{ \mathbb{Z}_{19}}\) czyli mnożysz obydwie strony kongruencji przez \(\displaystyle{ 9 .}\)