Modular Multiplicative Inverse Using EEA

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.