# Modular Multiplicative Inverse Using EEA

Use the Extended Euclid's algorithm to calculate the modular multiplicative inverse of a number.

## We'll cover the following

## Problem introduction

Write a program to calculate the multiplicative modulo inverse of `A`

with respect to `M`

. The modular multiplicative inverse is an integer `x`

such that.

```
A x ≅ 1 (mod M)
```

The multiplicative inverse of `A modulo M`

exists if, and only if, `A`

and `M`

are relatively prime, i.e., `gcd(A, M) = 1`

. The value of `x`

should be in `{0, 1, 2, … M-1}.`

Let us take the following example: `A = 3`

, `M = 11`

, so the output will be `x = 4`

since `(4*3) mod 11 = 1`

, `4`

is modulo inverse of 3 with respect to 11.
You might think, `15`

also as a valid output as `(15*3) mod 11`

is also 1, but 15 is not in the ring `{0, 1, 2, ... 10}`

, so it is not valid.

Let us see how the Extended Euclid’s algorithm can be used in this case. We know from the Extended Euclid’s algorithm that:

```
A.x + B. y = gcd(A, B)
```

To find the multiplicative inverse of `A`

under `M`

, we put `B = M`

in the above formula. Since we know that `A`

and `M`

are relatively prime, we can put the value of `gcd`

as 1.

```
A.x + M.y = 1
```

If we take `modulo M`

on both sides, we get

```
A.x + M.y ≅ 1 (mod M)
```

We can remove the second term on the left side as `M.y (mod M)`

would always be 0 for an integer `y`

.

```
A.x ≅ 1 (mod M)
```

So the `x`

that we can find using the Extended Euclid algorithm is the multiplicative inverse of `A`

.

## Solution

Now, let us move on to the implementation of this solution.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.