# modulo inverse

• Jun 16th 2011, 08:23 AM
dwsmith
modulo inverse
How do I solve:

$\displaystyle x\equiv 12^{-1} \ (\text{mod} \ 25)$

I know x = 23.
• Jun 16th 2011, 08:40 AM
melese
Re: modulo inverse
$\displaystyle 12^{-1}$ is the multiplicative inverse of $\displaystyle 12$ modulo $\displaystyle 25$ and satifies the congruence $\displaystyle 12x\equiv1\pmod{25}$. By inspection, $\displaystyle 12\cdot-2=-24\equiv1\pmod{25}$. Therefore, $\displaystyle x\equiv-2\equiv23\pmod{25}$.
• Jun 16th 2011, 08:42 AM
dwsmith
Re: modulo inverse
Quote:

Originally Posted by melese
$\displaystyle 12^{-1}$ is the multiplicative inverse of $\displaystyle 12$ modulo $\displaystyle 25$ and satifies the congruence $\displaystyle 12x\equiv1\pmod{25}$. By inspection, $\displaystyle 12\cdot-2=-24\equiv1\pmod{25}$. Therefore, $\displaystyle x\equiv-2\equiv23\pmod{25}$.

Why does negative 2 represent 12^{-1}?
• Jun 16th 2011, 09:52 AM
Deveno
Re: modulo inverse
whatever 12^(-1) (mod 25) is, it should be the case that 12(12^(-1)) = 1 (mod 25).

12(-2) = -24 = 1 - 25, so 12(-2) = 1 (mod 25).

similarly -2 = 23 (mod 25).

to explain properly why this works, note that gcd(12, 25) = 1.

this means we can find integers r,s with 12r + 25s = 1.

this equality still holds mod 25, so:

12r = 1 mod 25.

in this case, it is easy to see that r = -2 and s = 1 will work:

12(-2) + 25(1) = -24 + 25 = 1.

so 12(-2) = 1 (mod 25), but also:

(12)(-2) (mod 25) = (12 (mod 25))(-2 (mod 25)) = (12)(23).

but if we didn't guess r = -2, and s = 1 right off the bat, we could have calculated them like so:

25 = 12(2) + 1, (by the division algorithm)

so 1 = 25 - 12(2) = 25(1) + 12(-2) (running the division algorithm backwards,

to find the remainder (the gcd in this case) in terms of the numbers we're taking the gcd of).