[Math] Euclidean Algorithm for Modular Inverse, with negative numbers

chinese remainder theoremmodular arithmeticnumber theory

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?

Thanks in advance!

Best Answer

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.

Related Question