How do I solve:

I know x = 23.

Printable View

- Jun 16th 2011, 08:23 AMdwsmithmodulo inverse
How do I solve:

I know x = 23. - Jun 16th 2011, 08:40 AMmeleseRe: modulo inverse
is the multiplicative inverse of modulo and satifies the congruence . By inspection, . Therefore, .

- Jun 16th 2011, 08:42 AMdwsmithRe: modulo inverse
- Jun 16th 2011, 09:52 AMDevenoRe: 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).