Finding the correct $x$ to $ax - by = 1$

Question

I want to find the modular inverse of $5 \pmod {13}$ such that : $$ 5x - 13y = 1$$

I tried to use the Euclidean alogritm for the GCD and use the extension(Extended Euclidean Algorithm) to solve for x. Looks like this: \begin{align} 13 &= 5(2) + 3\\ 5 &= 3(1) + 2\\ 3 &= 2(1) + 1 \end{align}

Then the extended:

\begin{align} 1 &= 3 - 2(1)\\ &= 3 - 1(5 - 3(1))\\ &= 3(2) - 5\\ &= 2(13 - 5(2)) - 5\\ &= 2(13) - 5(4) - 5\\ &= 13(2) - 5(5)\\ \end{align}

After that , I found that something in my solution is wrong but I can't point where it is. Because I tried to substitute for $x$ with 5.

$$ 5(5) - 13(2) = -1 $$

It resulted $-1$ instead of $1.$

Note : I want $x$ to be a positive integer to make it applicable.

Answer 1

You proved correctly that$$13\times2-5\times5=1$$and this is the same thing as asserting that$$5\times(-5)-13\times(-2)=1.$$So, the inverse of $5$ modulo $13$ is $-5(=8)$.