## Table of Contents

- What is Multiplicative Inverse?
- What is Modular Multiplicative Inverse?
- How to find Multiplicative Inverse of a number modulo M i.e. under M?
- Brute Force Python Code to find Multiplicative Inverse of a number modulo M -
*O(M)* - Modular Multiplicative Inverse using Extended Euclid’s Algorithm
- Modular Multiplicative Inverse using Fast Power Algorithm

## What is Multiplicative Inverse?

Multiplicative Inverse of a number A is another number B, such that A x B equals 1. Multiplicative Inverse of a number A is denoted as A^{-1}, and A x A^{-1} = 1. For example: multiplicative inverse of 3 is 1/3 because 3 x 1/3 = 1.

## What is Modular Multiplicative Inverse?

In modular arithmetic, we don’t have the `/`

division operator. However, we have `%`

modulo operator which helps in finding Modular Multiplicative Inverse.

Modular Multiplicative Inverse of a number A in the range M is defined as a number B such that (A x B) % M = 1.

Important points to note:

- Modulo inverse exists only for numbers that are co-prime to M.
- If (A x B) % M = 1, then B lies in the range [0, M-1]

## How to find Multiplicative Inverse of a number modulo M i.e. under M?

We know for a fact that, if multiplicative inverse for a number exists then it lies in the range [0, M-1]. So the basic approach to find multiplicative inverse of A under M is:

- Iterate from
`0`

to`M-1`

, call it`i`

- Check if
`(A x i) % M`

equals`1`

- If yes, then we have
`i`

as multiplicative inverse of`A`

under`M`

## Brute Force Python Code to find Multiplicative Inverse of a number modulo M - *O(M)*

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

def modulo_multiplicative_inverse(A, M):

"""

Returns multiplicative modulo inverse of A under M, if exists

Returns -1 if doesn't exist

"""

# This will iterate from 0 to M-1

for i in xrange(0, M):

# If we have our multiplicative inverse then return it

if (A*i) % M == 1:

return i

# If we didn't find the multiplicative inverse in the loop above

# then it doesn't exist for A under M

return -1

print modulo_multiplicative_inverse(5, 11)

# Output: 9 (Because 5*9 % 11 => 45 % 11 = 1)

print modulo_multiplicative_inverse(3, 8)

# Output: 3 (Because 3*3 % 8 => 9 % 8 = 1)

print modulo_multiplicative_inverse(5, 25)

# Output: -1 (Because 5 and 25 are not co-primes, so it doesn't exist)

The above implementation is a brute force approach to find Modular Multiplicative Inverse. Time Complexity is *O(M)*, where M is the range under which we are looking for the multiplicative inverse. However, this method fails to produce results when M is as large as a billion, say 1000000000. Try out using A = 23 and M = 1000000007. Can we do any better?

## Modular Multiplicative Inverse using Extended Euclid’s Algorithm

We will not get deeper into Extended Euclid’s Algorithm right now, however, let’s accept the fact that it finds `x`

and `y`

such that `a*x + b*y = gcd(a, b)`

. Let’s see how we can use it to find Multiplicative Inverse of a number A modulo M, assuming that A and M are co-prime.

- Using A in place of
`a`

and M in place of`b`

in the equation, we have`A*x + M*y = gcd(A, M)`

. - We know Greatest Common Divisor (GCD) of two co-prime numbers is 1. So now we have,
`A*x + M*y = 1`

- Taking modulo with M on both sides we have,
`(A*x) % M + (M*y) % M = 1 % M`

, which results into`(A*x) % M = 1 % M`

(because`(M*y) % M`

is 0) - Voila, what do we call
`x`

if`(A*x) % M = 1 % M`

?`x`

is our answer, i.e. multiplicative inverse of A under M.

Now, for any two numbers `a`

and `b`

Extended Euclid’s Algorithm finds three things: `gcd(a, b)`

, `x`

and `y`

such that `a*x + b*y = gcd(a, b)`

.
Please consider reading about Extended Euclid’s Algorithm^{1}.

### Python Implementation - *O(log M)*

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

def modulo_multiplicative_inverse(A, M):

"""

Assumes that A and M are co-prime

Returns multiplicative modulo inverse of A under M

"""

# Find gcd using Extended Euclid's Algorithm

gcd, x, y = extended_euclid_gcd(A, M)

# In case x is negative, we handle it by adding extra M

# Because we know that multiplicative inverse of A in range M lies

# in the range [0, M-1]

if x < 0:

x += M

return x

def extended_euclid_gcd(a, b):

"""

Returns a list `result` of size 3 where:

Referring to the equation ax + by = gcd(a, b)

result[0] is gcd(a, b)

result[1] is x

result[2] is y

"""

s = 0; old_s = 1

t = 1; old_t = 0

r = b; old_r = a

while r != 0:

quotient = old_r/r

# This is a pythonic way to swap numbers

# See the same part in C++ implementation below to know more

old_r, r = r, old_r - quotient*r

old_s, s = s, old_s - quotient*s

old_t, t = t, old_t - quotient*t

return [old_r, old_s, old_t]

print modulo_multiplicative_inverse(5, 11)

# Output: 9 (Because 5*9 % 11 => 45 % 11 = 1)

print modulo_multiplicative_inverse(3, 8)

# Output: 3 (Because 3*3 % 8 => 9 % 8 = 1)

print modulo_multiplicative_inverse(23, 1000000007)

# Output: 739130440 (Because 739130440*23 = 17000000120 and 17000000120 % 1000000007 is 1)

Time Complexity of the above approach is *O(log(A) + log(M))*.

### C++ Implementation - *O(log M)*

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

#include <iostream>

#include <vector>

using namespace std;

vector<long long> extended_euclid_gcd(long long a, long long b) {

// Returns a vector `result` of size 3 where:

// Referring to the equation ax + by = gcd(a, b)

// result[0] is gcd(a, b)

// result[1] is x

// result[2] is y

long long s = 0; long long old_s = 1;

long long t = 1; long long old_t = 0;

long long r = b; long long old_r = a;

while(r != 0) {

long long quotient = old_r/r;

// We are overriding the value of r, before that we store it's current

// value in temp variable, later we assign it to old_r

long long temp = r;

r = old_r - quotient*r;

old_r = temp;

// We treat s and t in the same manner we treated r

temp = s;

s = old_s - quotient*s;

old_s = temp;

temp = t;

t = old_t - quotient*t;

old_t = temp;

}

vector<long long> result;

result.push_back(old_r);

result.push_back(old_s);

result.push_back(old_t);

return result;

}

long long modulo_multiplicative_inverse(long long A, long long M) {

// Assumes that A and M are co-prime

// Returns multiplicative modulo inverse of A under M

// Find gcd using Extended Euclid's Algorithm

vector<long long> v = extended_euclid_gcd(A, M);

long long gcd = v[0];

long long x = v[1];

long long y = v[2]; // We don't really need this though

// In case x is negative, we handle it by adding extra M

// Because we know that multiplicative inverse of A in range M lies

// in the range [0, M-1]

if(x < 0) {

x += M;

}

return x;

}

int main() {

cout << modulo_multiplicative_inverse(5, 11) << endl;

// Output: 9 (Because 5*9 % 11 => 45 % 11 = 1)

cout << modulo_multiplicative_inverse(3, 8) << endl;

// Output: 3 (Because 3*3 % 8 => 9 % 8 = 1)

cout << modulo_multiplicative_inverse(23, 1000000007) << endl;

// Output: 739130440 (Because 739130440*23 = 17000000120 and 17000000120 % 1000000007 is 1)

return 0;

}

At times, Extended Euclid’s algorithm is hard to understand. There is one easy way to find multiplicative inverse of a number A under M. We can use fast power algorithm for that.

## Modular Multiplicative Inverse using Fast Power Algorithm

Pierre de Fermat^{2} once stated that, if M is prime then, A^{-1} = A^{M-2} % M. Now from Fast Power Algorithm, we can find A^{M-2} % M in *O(log M)* time.

### Python Implementation - *O(log M)*

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

def modulo_multiplicative_inverse(A, M):

"""

Assumes that M is a prime number

Returns multiplicative modulo inverse of A under M

"""

return fast_power(A, M-2, M)

def fast_power(base, power, MOD):

"""

Returns the result of a^b i.e. a**b

We assume that a >= 1 and b >= 0

Remember two things!

- Divide power by 2 and multiply base to itself (if the power is even)

- Decrement power by 1 to make it even and then follow the first step

"""

result = 1

while power > 0:

# If power is odd

if power % 2 == 1:

result = (result * base) % MOD

# Divide the power by 2

power = power / 2

# Multiply base to itself

base = (base * base) % MOD

return result

print modulo_multiplicative_inverse(5, 11)

# Output: 9 (Because 5*9 % 11 => 45 % 11 = 1)

print modulo_multiplicative_inverse(3, 8)

# Output: 3 (Because 3*3 % 8 => 9 % 8 = 1)

print modulo_multiplicative_inverse(23, 1000000007)

# Output: 739130440 (Because 739130440*23 = 17000000120 and 17000000120 % 1000000007 is 1)

### C++ Implementation - *O(sqrt(N))*

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

#include <iostream>

using namespace std;

long long fast_power(long long base, long long power, long long MOD) {

long long result = 1;

while(power > 0) {

if(power % 2 == 1) { // Can also use (power & 1) to make code even faster

result = (result*base) % MOD;

}

base = (base * base) % MOD;

power = power / 2; // Can also use power >>= 1; to make code even faster

}

return result;

}

long long modulo_multiplicative_inverse(long long A, long long M) {

// Assumes that M is a prime number

// Returns multiplicative modulo inverse of A under M

return fast_power(A, M-2, M);

}

int main() {

cout << modulo_multiplicative_inverse(5, 11) << endl;

// Output: 9 (Because 5*9 % 11 => 45 % 11 = 1)

cout << modulo_multiplicative_inverse(3, 8) << endl;

// Output: 3 (Because 3*3 % 8 => 9 % 8 = 1)

cout << modulo_multiplicative_inverse(23, 1000000007) << endl;

// Output: 739130440 (Because 739130440*23 = 17000000120 and 17000000120 % 1000000007 is 1)

return 0;

}

Note that this method works when M is a prime number. Time Complexity of the above algorithm is also *O(log M)*.

References:

- [1]: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
- [2]: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Got a burning question you wanna get answered? Ask it in the comments.