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!

  • $\begingroup$ 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. $\endgroup$ – Mark Bennet Apr 21 '14 at 19:10
  • $\begingroup$ Hint $\ {\rm mod}\ 12\!:\ n\equiv n+12\equiv n+24\equiv n+36\equiv \,\ldots\ \ $ $\endgroup$ – Bill Dubuque Apr 21 '14 at 19:10
  • $\begingroup$ Can’t you just do it by inspection? $7\cdot11=6\cdot12+5$, $11$ is the solution. $\endgroup$ – Lubin Apr 21 '14 at 19:32
  • $\begingroup$ Yeah I got it by inspection, but I'm looking for a way to get it when I can't get there that way. I'm keeping an eye on my EEA and I notice my problem was that i was doing ax+by=d for both positives, when my b is -12 (in this case). I'm doing wrong the negative divisions, I guess (ie, 7/-12?) $\endgroup$ – Blasted Apr 21 '14 at 19:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.