C.R.T. .com
It doesn't have to be difficult if someone just explains it right.

How to calculate the Modular Multiplicative Inverse

Here we explain how you can calculate the multiplicative inverse in the Chinese Remainder Theorem.

Using this simple calculator

Pro: you immediately get the answer you're looking for.
Con: you don't get to see how it has been calculated.

Using the Extended Euclidean Algorithm

Pro: the most populair way. Always works if there exists a modular multiplicative inverse for the input numbers.
Con: a lot of work if you do it on paper instead of using a computer program.
So if you're going to do the Chinese Remainder Theorem by hand, it might be a good idea to calculate the multiplicative inverse using a calculator anyway.

Here are the sources you need, depending on what you want

Find it by trying

Pro: if you're lucky, it's not much work.
Con: unbdoable for big numbers. And it makes you look like a noob.

Here's how it works

a and b are multiplicative inverse modulo m of each other,
if a × b (mod m) ≡ 1 (mod m).
So if you want to calculate the multiplicative inverse of a (mod m), you can just try to multiply a by several numbers (mod m).
You stop once you find an answer that is equivalent to 1 (mod m), or if the number you multiply with (i.e. b) is equal to m.


Calculate the multiplicative inverse of 3 (mod 7).

OK, so a=3 and m=7. Now we have to find b such that a × b (mod m) ≡ 1 (mod m).
Let's start with b=0 and then add 1 to it until we found the answer.
3 × 0 (mod 7) ≡ 0 (mod 7)
3 × 1 (mod 7) ≡ 3 (mod 7)
3 × 2 (mod 7) ≡ 6 (mod 7)
3 × 3 (mod 7) ≡ 9 (mod 7) ≡ 2 (mod 7)
3 × 4 (mod 7) ≡ 12 (mod 7) ≡ 5 (mod 7)
3 × 5 (mod 7) ≡ 15 (mod 7) ≡ 1 (mod 7)

And there it is: 3 × 5 (mod 7) ≡ 1 (mod 7)
So b=5. The multiplicative inverse of 3 (mod 7) is 5.
Now you look like a noob, but who cares, we found the answer. The people laughing at you can only wish they would know the answer.

If the answer wouldn't be 1 with b=5, we would have on more step:
3 × 6 (mod 7) ≡ 18 (mod 7) ≡ 4 (mod 7)
And then we would give up, because in the next step b would be equal to n.
This means b (mod n) would be 0. We already tried 0, so that would mean we would start over.

Euler's Theorem

Pro: you don't have to use the Extended Euclidean Algorithm
Con: You have to know Φ(m), which kind of sucks to calculate.

Here is how it works.

where a-1 is the modular multiplicative inverse of a (mod m).
So if we have an a and we also know Φ(m), we can calculate the multiplicative inverse of a (mod m) by calculating aΦ(m)-1(mod m)

For calculating Φ(m), you can use this calculator


Find the multiplicative inverse of 8 mod 77.

we have a=8 and m=77. So we can calculate it as follows:
aΦ(m)-1(mod m) =
8Φ(77)-1(mod 77) =
OK, now we put 77 in the calculator above to get Φ(77). We see that it equals 60. So we continue our calculation:
8Φ(77)-1(mod 77) =
860-1(mod 77) =
859(mod 77) =
29 (mod 77) =

So the multiplicative inverse of 8 mod 77 is 29.

Another example

Find the multiplicative inverse of 7 mod 15.

a=7, m=15. So Φ(m) = Φ(15) = 8.
aΦ(m)-1(mod m) = 7Φ(15)-1(mod 15) = 77(mod 15) = 13 (mod 15)

So the multiplicative inverse of 7 mod 15 is 13.