Finding inverses mod n

[Kevin Lin]

Hi all,

Today a few people have asked me the question: What if, when computing the inverse of a number mod n, we get a negative number?

Well, this is no problem at all. First of all, there's nothing wrong with negative numbers. Second of all, if you don't like negative numbers, if you're working mod n, then you can always add multiples of n to your result until you get a positive number.

This might happen, for example, when we are computing d, which is the inverse of e modulo (p-1)(q-1), which we need for RSA decryption. In this case, whatever number you get for d, you can always add multiples of (p-1)(q-1) until you get a positive number.

For example, an inverse of 5 mod 8 is -3 (since 5*(-3) mod 8 = -15 mod 8 = 1), but -3+8=5 is another inverse of 5 mod 8 (since 5*5 mod 8 = 25 mod 8 = 1). And similarly -3+8+8=13 is another inverse of 5 mod 8 (since 5*13 mod 8 = 65 mod 8 = 1).

Hope that helps,

Kevin