# 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.

**Simple calculator for the modular multiplicative inverse**

Calculate the multiplicative inverse of **a** mod **m**.

**Answer:**

The answer will appear here if you enter some numbers and click calculate.

#### 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__

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

Proceed as follows:

#### 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`

.

__Example__

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`

is the modular multiplicative inverse of ^{-1}`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

**Simple calculator for the Euler Totient Function**

Calculate **Φ(m)** for the given **m**

**Answer:**

Enter a number for m and click on 'Calculate' to show Φ(m).

Φ(0) = 1

__Example__

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)

`8`

= ^{60-1}(mod 77)

`8`

= ^{59}(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`

.

Answer:

a=7, m=15. So Φ(m) = Φ(15) = 8.

`a`

= ^{Φ(m)-1}(mod m)`7`

= ^{Φ(15)-1}(mod 15)`7`

= ^{7}(mod 15)`13 (mod 15)`

So the multiplicative inverse of 7 mod 15 is 13.