How do I solve:
I know x = 23.
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).