# Euclidean Algorithm for Modular Inverse, with negative numbers

I might be on to something quite simple which I'm failing to see, while calculating modular inverses.

For example, calculating 7x = 5 (mod 12)

Which is the same as saying: 7x - 5 = 12k

Which becomes: 7x - 12k = 5

And then I proceed using Euclidean Algorithm for x,k. I get to -25 and 15 respectively. However, I need the x to be positive to get the inverse I'm looking for. How can I get a positive modular inverse?

• note that $7\cdot -25 -12\cdot 15 = -175-180=-355$ while $7\cdot -25 - 12 \cdot -15=5$ so you may want to check your signs. – Mark Bennet Apr 21 '14 at 19:10
• Hint $\ {\rm mod}\ 12\!:\ n\equiv n+12\equiv n+24\equiv n+36\equiv \,\ldots\ \$ – Bill Dubuque Apr 21 '14 at 19:10
• Can’t you just do it by inspection? $7\cdot11=6\cdot12+5$, $11$ is the solution. – Lubin Apr 21 '14 at 19:32
In a Bezout identity $$a⋅x+b⋅y=c$$ you can exchange multiples of $a⋅b$ or even $lcm(a,b)=a'\cdot b=a\cdot b'$ between the terms on the left, so that $$a⋅(x-k⋅b')+b⋅(y+k⋅a')=c$$ is also a correct identity. This slightly extends the reasoning on modular equivalences in the comment of Bill Dubuque.