Odwrócony algorytm euklidesa

[Cesar]

Mam problem ze zrozumeniem jak przy pomocy algorytmu Euklidesa znajdujemy element odwrotny..
np. \(15^{-1}=?\) w \(Z_{53}\)
Wiem jak bedzie wyglądał algorytm Euklidesa ale nie wiem na jakiej zasadzie się go odwraca

[irena]

\(15\cdot x\equiv1(mod53)\)

\(53=3\cdot15+8\\15=8+7\\8=7+1\)

\(1=8-7=(53-3\cdot15)-(15-8)=53-3\cdot15-15+53-3\cdot15=2\cdot53-7\cdot15\)

\(15^{-1}\equiv-7\ (mod53)\equiv46\ (mod53)\)

[patryk00714]

innymi słowy mamy znaleźć takie \(q=15^{-1}\), aby:

\(15 \cdot q=1\)

aby wyliczyć q szybko i bez wyznaczania tabelki stosujemy następujący algorytm. Zapisujemy następującą macierz :

\(\begin{bmatrix}1& 0&53 \\ 0&1&15\\\end{bmatrix}\) i rozwiązujemy ją, jakby od tyłu tak, aby wyraz \(A_{1,3}=1\)

\(\begin{bmatrix}1& 0&53 \\ 0&1&15\\\end{bmatrix} \to ^{w_1 \to w_1-3w_2}]\begin{bmatrix}1& -3&8 \\ 0&1&15\\\end{bmatrix} \to ^{w_2 \to w_2-w_1}\begin{bmatrix}1& -3&8 \\ -1&4&7\\\end{bmatrix} \Rightarrow ^{w_1 \Rightarrow w_1-w_2}\)

\(\begin{bmatrix}2& -7&1 \\ -1&4&7\\\end{bmatrix}

\(53 \cdot 2-7 \cdot 15 =1\)

\(15^{-1}\equiv-7(mod53)\)

\(15^{-1}\equiv46(mod53)\)\)

[dilqwz]

@patryk00714 czy mógłbyś napisać jak nazywa się to co zrobiłeś?

[patryk00714]

nie ma to swojej fachowej nazwy z tego co pamiętam. Mieliśmy tę metodę przy okazji wprowadzenia eliminacji Gaussa.