# Euclid Algorithm to Find Muliplicative Inverse

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.

• The inerse is $-3$ here, which is congruent to $26$ – Peter Oct 12 at 14:02
• Instead of rote rule application to the Bezout identity you should remember its genesis, viz. reducing $\, a n + b m = 1\,$ modulo $n$ yields $\,bm\equiv 1\,$ so $\, m\equiv b^{-1}\pmod{\!n}.\,$ In your case $\, b = -3\,$ (you forgot to include the sign). Generally one should always strive to remember the conceptual heart of the matter vs. rote rules. – Bill Dubuque Oct 12 at 14:17
• Btw, it is easier and far less error-prone to forward propagate the equations, e.g. see here and here. – Bill Dubuque Oct 12 at 15:26
• @BillDubuque Do you agree with my suggested choice of duplicate? – Jyrki Lahtonen Oct 13 at 9:23
• FWIW I haven't downvoted on the answers here even though I am tempted, and encourage the practice. A site this age has certainly covered all the nooks and corners of Euclid, so it behooves 20k+ users to search first. When they obviously don't, a downvote is A) a reminder, B) a gesture of strong disproval. – Jyrki Lahtonen Oct 13 at 9:25

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

• Since this is the first answer, I want to give a credit to this one. I have only one question. Why $-3\equiv 26$ – Emrah Sariboz Oct 12 at 14:17
• @user109067 Because $\,29\,$ divides $\,-3-26\ \$ – Bill Dubuque Oct 12 at 14:21
• @user109067 Because $-3+29=26$ – user Oct 12 at 14:22
• sorry still not clear. What you mean 29 divides -3? – Emrah Sariboz Oct 12 at 14:23
• @user109067 $\ -3-26 = -29\$ is divisible by $29.\$ Recall $\ a\equiv b\pmod n\$ means $a-b$ is divisible by $n\ \$ – Bill Dubuque Oct 12 at 14:24

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

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

• This is a correct explanation, so why was it downvoted? – Bill Dubuque Oct 12 at 14:07
• @BillDubuque The ways of the downvote fairies are ineffable. But yeah, I'm wondering that too. I mean, there are other correct answers here, but I feel my approach is at least a tiny bit distinct. – Arthur Oct 12 at 14:08