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.