**Modular multiplicative inverse** of a number *a mod* * m *is a number

**such that**

*x**ax ≡ 1 (mod m)*

It is very helpful where division is carried out along with modular operation. Instead of dividing by a number, its inverse can be multiplied to fetch the same result i.e.

*k/a mod m = k*x mod m*

Modular multiplicative inverse can be find only if the two numbers are coprimes i.e. their gcd is 1.

Here we are using **Extended Euclidean Algorithm** to find the inverse.

The algorithm is same as **Euclidean algorithm** to find **gcd** of two numbers. Euclid’s algorithm starts with the given two integers and forms a new pair that consists of the smaller number and the remainder of the division of larger number with smaller number numbers. The new pair again applied given algorithm until the remainder is zero. The only extension in extended euclidean algorithm is that every divisor and remainder is represented as linear combination of the original two numbers and coefficients are stored in every iteration.

**Algorithm:**

We have to find x such that *ax ≡ 1 (mod m)*

Above equivalence can be stated alternatively as:

*ax = pm + 1*

or ** ax + my = 1** known as Bézout’s identity.

The beginning two numbers are *a* and *m*

** x** and

**are coefficients of**

*y**a*and

*m*respectively when dividend is represented as linear combination of

*a*and

*m*.

**and**

*u***are coefficients of**

*v**a*and

*m*respectively when divisor is represented as linear combination of

*a*and

*m*.

**and**

*c***are coefficients of**

*d**a*and

*m*respectively when remainder is represented as linear combination of

*a*and

*m*.

Initially dividend is *m* and divisor is *a*

*m = 0*a + 1*m = x*a + y*m*

*a = 1*a + 0*m = u*a + v*m*

So *x = 0, y = 1, u = 1, v = 0*

*m = q*a + r* where *q* is quotient and *r* is remainder.

From next iteration *q* acts as dividend and *r* as divisor. Let *e* is dividend and *f* is divisor in iteration.

*e = q*f + r*

*r = (-q)*f + 1*e = (-q)*(u*a + v*m) + 1*(x*a + y*m) = (x – u*q)*a + (y – v*q)*m*

So

*c = x – u*q*

* d = y – v*q*

For next iteration roles will be switched as:

*f* is dividend ⇒ *e = f*

*r* is divisor ⇒ *f = r*

*x = u*

* y = v*

* u = c*

* v = d*

**Termination:**

When *r* is *1*

*r = c*a + d*m = 1*

*c* is the required modular inverse.

**Example:**

Consider example of two numbers * a = 29, m = 168*

*29x + 168y = 1*

* 168 = 0*29 + 1*168 *

* 29 = 1*29 + 0*168 *

**First Step:**

*168 = 5*29 + 23 *

*23 = (-5)*29 + 1*168 = (-5)*[1*29 + 0*168] + 1*[0*29 + 1*168]*

**Second Step:**

*29 = 1*23 + 6*

* 6 = 1*29 + (-1) *23 = 1*[0*168 + 1*29] + (-1)*[(-5)*29 + 1*168] = 6*29 + (-1)*168*

**Third Step:**

*23 = 3*6 + 5*

* 5 = 1*23 + (-3)*6 = 1*[ (-5)*29 + 1*168] + (-3)*[6*29 + (-1)*168] = (-23)*29 + 4*168*

**Fourth Step:**

*6 = 1*5 + 1*

* 1 = (-1)*5 + 1*6 = (-1)*[(-23)*29 + 4*168] + 1*[6*29 + (-1)*168] = 29*29 + (-5)*168*

Hence final solution comes as:

*29*29 + (-5)*168 = 1*

* x = 29 *and* y = (-5)*

**C/C++ Implementation:**

```
int modmulinverse(int a,int m)
{
int x = 0,y = 1,u = 1,v = 0;
int e = m,f = a;
int c,d,q,r;
while(f != 1)
{
q = e/f;
r = e%f;
c = x-q*u;
d = y-q*v;
x = u;
y = v;
u = c;
v = d;
e = f;
f = r;
}
u = (u+m)%m;
return u;
}
```