Modular Multiplicative Inverses

Question

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

Answer 1

There is no mistake. $-5$ and $8$ are just equal mod $13$. They are the same number.

Answer 2

Remember $a\equiv b \pmod n$ if $a-b$ or $b-a$ is a multiple of $n$. You have $-5\equiv 8 \pmod {13}$ because $8-(-5) = {13}$ is a multiple of $13$.

Answer 3

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}$$