Euclid Algorithm to Find Muliplicative Inverse

Question

Here I am trying to find the multiplicative inverse of 19 respect to 29.

$$19x \equiv 1 \pmod{29} $$

What I tried

\begin{align*} 29 &= 1(19) + 10\\\ 19 &= 1(10) + 9\\\ 10 &= 1(9) + 1. \end{align*}

From backtracking, I came up with the

\begin{align*} 1 &= 2(29) - 3(19)\\\ \end{align*}

However, 3 is not a multiplicative inverse of the 29. Where am I making a mistake?

I looked many answers including this answer; however, couldn't figure out my mistake.

Answer 1

What you have found indeed is that $-3\equiv 26$ is the multiplicative inverse of $19$ $\mod 29$.

Answer 2

Reducing your backtracking result modulo $29$, it becomes $$ 1\equiv -3\cdot 19\pmod{29} $$ Which is to say, the multiplicative inverse of $19$ is $-3$.

Answer 3

You're almost there! Multiply both sides by $-3$ and you have $$-57x\equiv -3\pmod {29}\\x\equiv-3\equiv26\pmod{29}$$