2
$\begingroup$

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!

$\endgroup$
4
  • $\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
    Commented Apr 21, 2014 at 19:10
  • $\begingroup$ Hint $\ {\rm mod}\ 12\!:\ n\equiv n+12\equiv n+24\equiv n+36\equiv \,\ldots\ \ $ $\endgroup$
    – Bill Dubuque
    Commented Apr 21, 2014 at 19:10
  • $\begingroup$ Can’t you just do it by inspection? $7\cdot11=6\cdot12+5$, $11$ is the solution. $\endgroup$
    – Lubin
    Commented Apr 21, 2014 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
    Commented Apr 21, 2014 at 19:45

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .