<s>[INST] Modular Multiplicative Inverses I'm in a cryptography and struggling with understanding how the Euclidean Algorithm necessarily works for finding multiplicative inverses. We haven't actually covered the algorithm yet, just a way to brute force finding the inverses but I like working with an algorithm instead of just guess and checking so I learned it myself. In the equation 1/5 mod 13 I understand that this is equivalent to 5x = 1 mod 13 however when going through the algorithm I get the answer to be -5 instead of 8 which it is supposed to be. Can anyone shed some light on where I'm going wrong? Here's my work.
(a) 1/5 mod 13 
1/5 mod 13 ≡ 5-1 mod 13 ≡ 5x = 1 (mod 13)
13 = 2(5) + 3
5 = 1(3) + 2
3 = 1(2) + 1
GCD of 13 and 5 is 1.
1 = 3 – 2(1)
= 3 – (5 – 3(1)) = 3 - 5 + 3 = 2(3) - 5 
= 2(13 - 2(5)) - 5 
= 2(13) – 4(5) – 5
= 2(13) -5(5)
-> mod 13 on both sides
1 mod 13 = 0 – 5(5) mod 13
1 = -5(5) mod 13
x = -5
 [/INST] You are right indeed by Euclidean algorithm we have


*

*$13=5\cdot 2+\color{red}3$

*$5=\color{red}3\cdot 1+\color{red}2$

*$3=\color{red}2\cdot 1+1$


and therefore starting from the last one
$$1=3-2=3-(5-3)=2\cdot 13-2\cdot 5\cdot 2-5 \implies  2\cdot 13-5\cdot 5=1 $$$$\implies -5\cdot 5=1-2\cdot 13$$
and then
$$5x\equiv 1 \pmod {13} \implies x\equiv -5 \equiv 8 \pmod {13}$$
</s>