Thread: modulo inverse

How do I solve:



I know x = 23.

is the multiplicative inverse of modulo and satifies the congruence . By inspection, . Therefore, .

Originally Posted by melese

is the multiplicative inverse of modulo and satifies the congruence . By inspection, . Therefore, .

Why does negative 2 represent 12^{-1}?

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).