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.

• Just want the answer?
  Skip the Extended Euclidean Algorithm and use the calculator above. It uses the Extended Euclidean Algorithm for you, so you don't have to worry about that. Just fill in the numbers, click calculate and then use the answer in your calculation for the Chinese Remainder Theorem.
• Do you want a calculator that shows you the intermediate steps?
  Have a look at the calculator on ExtendedEuclideanAlgorithm.com.
  It shows you a table with all the steps in it, a step-by-step solution to derive the answer and a verification that the answer is correct.
  It's verify useful if you need to write down the intermediate steps while calculating the multiplicative inverses, but don't want to do this by hand.
  If you don't understand the output of the calculator, don't panic. Just have a look at the bullet point below.
  
• Do you want to do it yourself and/or understand the steps in that calculator on ExtendedEuclideanAlgorithm.com?
Have a look at the pages with explanations.
Proceed as follows:
1. First, make sure you understand the Euclidean Algorithm.
   Here's a link to a page that explains the Euclidean Algorithm and how to put it in a table.
2. Second, learn how to use the Extended Euclidean Algorithm in general.
   So not necessarily for calculating the multiplicative inverse, but also for other things. Here's the page explaining the Extended Euclidean Algorithm.
3. And finally,
   see how to use the Extended Euclidean Algorithm to calculate the modular multiplicative inverse. If you still don't know what a multiplicative inverse is at this point, don't worry. We don't judge, we help. It's explained on that page as well.

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.

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.

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.

Answer:
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.

Find the multiplicative inverse of 7 mod 15.

Answer:
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.