Modular Multiplicative Inverse

Modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m.  We can write this,

                                                          

                                              

                                                      

                                            

Here a and m must be relatively prime. It can be proven that the modular inverse exists if and only if a and m are relatively prime. 

Now we can write this, 

                                    

                                           a.x ⩭ 1 (mod m)

                                           a.x = 1 + y.m

                                           a.x - y.m = 1

                                           a.x + (-y).m = 1

a.x + (-y).m = 1, this equation solve by Extended GCD algorithm and from this we get x and y,  here value of x is inverse of a.

Notice that from Extended GCD algorithm the resulting x may be negative. So (x mod m)

might also be negative.

 

For this reason we can modify this x,                  

                                         x = (x%m + m) % m

                                                

#include<bits/stdc++.h>

#define ll long long int

using namespace std;

ll gcd(ll a, ll b, ll &x, ll &y)

{

if(b == 0)

{

x = 1;

y = 0;

return a;

}

ll x1, y1;

ll r = gcd(b, a%b, x1, y1);

x = y1;

y = x1 - (a/b) * y1;

return r;

}

void inverse_mod(ll a, ll m)

{

ll x, y;

ll g = gcd(a, m, x, y);

if(g != 1)

cout << "\nModular Inverse Impossible." << "\n";

else

{

ll r = (x%m + m)%m;

cout << "\nModular Inverse x :: " << r << "\n";

}

}

int main()

{

ll a, m;

cout << "Enter a and m :: ";

cin >> a >> m;

inverse_mod(a, m);

return 0;

}