Multiplicative Inverse

Pradipta Choudhury
Last Updated: May 13, 2022

Introduction:

In modular multiplicative inverse, two numbers are provided, ‘a’ and ‘m’, such that the  given condition is satisfied:


 <math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mi>a</mi><mi>x</mi><mo>&#xA0;</mo><mo>&#x2245;</mo><mn>1</mn><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi></mrow></mfenced><mspace linebreak="newline"/></mstyle></math>

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><mi>o</mi><mi>r</mi><mo>,</mo><mo>&#xA0;</mo><mi>a</mi><mi>x</mi><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi><mo>=</mo><mn>1</mn></mrow></mstyle></math>

The value of ‘x’ lies in the range of {1, 2, 3, …, m - 1}.

Note: ‘x’ can never become 0. As a * 0 mod ‘m’ can never be 1.
 

If you know the values of ‘a’ and ‘m’, how can you figure out the value of ‘x’? Come, let’s figure it out in detail.

 

Working:

So, through this approach, we are looking for an integer solution for ‘x’. Let’s take an example, 


<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><mfenced><mrow><mn>5</mn><mo>&#xD7;</mo><mi>x</mi></mrow></mfenced><mo>&#xA0;</mo><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mn>7</mn><mo>&#xA0;</mo><mo>=</mo><mo>&#xA0;</mo><mn>3</mn></mrow></mstyle></math>

In other words, what we need to multiply with 5 and divide the result by 7, such that 3 becomes the remainder
 

One way to solve for x is the brute force approach. In the brute force approach, values from 1 to (m - 1) are plotted in the equation and are checked if the given criterion is fulfilled. In the above example, values from 1 to 6 are plotted and checked to see if they produce the result we are looking for. 

The multiplicative inverse of a mod m exists if gcd(a,m) is 1 or a and m are relatively prime. 

If a=5 and m=7, the output will be 3. Since 5 * 3 mod 713 is modulo inverse of 5(under 7). 

 

C++ code for brute force approach:

Naive Approach:

/*
C++ naive approach code to find
The multiplicative inverse of a mod m
*/
#include <iostream>
using namespace std;

/*
A function that returns the value of x
calculated in basic approach
*/
int Find_mod_Inverse(int a, int m)
{
    for (int i = 1; i < m; i++)
    {
        if (((a % m) * (i % m)) % m == 1)
        {
            // Here i is the value of x
            return i;
        }
    }
}

// Driver code
int main()
{
    int a = 5, m = 7;
    cout<<"The value of x is"<<" ";
    
    // Function call
    cout << Find_mod_Inverse(a, m);
    return 0;
}

 

Output:

The value of x is 3

 

Time Complexity: O(m) 

In the naive approach, we check for every number from 1 to m, so, the time complexity is O(m).

 

Space Complexity: O(1)

As constant space is used in this approach hence, the space complexity is O(1).

 

Efficient Approach:

This approach can only work if ‘a’ and ‘m’ are coprime to each other, i.e., gcd(a, m) = 1. The main idea is based on an extended Euclid algorithm. The idea is to take two integers a and b and find their gcd as well as the value of x and y.


<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="18px"><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>b</mi><mi>y</mi><mo>=</mo><mi>g</mi><mi>c</mi><mi>d</mi><mfenced><mrow><mi>a</mi><mo>,</mo><mi>b</mi></mrow></mfenced></mrow></mstyle></math>

To simplify the equation further, we put b = m. Since we already know that the gcd of a and m is prime, we can use the gcd value as 1.

Taking modulo in both sides, the equation becomes:

<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>m</mi><mi>y</mi><mo>=</mo><mn>1</mn></mrow></mstyle></math>
<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><mi>a</mi><mi>x</mi><mo>+</mo><mi>m</mi><mi>y</mi><mo>&#xA0;</mo><mo>&#x2245;</mo><mo>&#xA0;</mo><mn>1</mn><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi></mrow></mfenced></mrow></mstyle></math>

The second term can be easily removed as for any integer y, taking mod with m is always zero. So, the final equation looks like this:

x can be found out using the Extended Euclid Algorithm, which is the multiplicative inverse of a.<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><mi>a</mi><mi>x</mi><mo>&#x2245;</mo><mn>1</mn><mo>&#xA0;</mo><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi></mrow></mfenced></mrow></mstyle></math>

Recursive Approach using Extended Euclid’s Algorithm:

 

/*
  C++ code for modular multiplicative 
  inverse using an efficient approach of
  Extended Euclid Algorithm
*/
#include <iostream>
using namespace std;

// Function for extended Euclidean Algorithm
int Find_gcd_Extended(int a, int b, int* x, int* y);

// Function to find modulo inverse of a
void Find_mod_Inverse(int a, int m)
{
    int x, y;
    int g = Find_gcd_Extended(a, m, &x, &y);
    
    /*
      If the gcd value doesn't matches 
      to 1, then inverse doesn't exist
    */
    if (g != 1)
    {
        cout << "Inverse doesn't exist";
    }
    else
    {
        /*
          m is added once more to handle
          negative values
        */
        int res = (x % m + m) % m;
        cout<<res<<endl;
    }
}

// Function to find extended Euclidean Algorithm
int Find_gcd_Extended(int a, int b, int* x, int* y)
{
    
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }
    
    // Storing results of recursive call
    int x1, y1;
    int gcd = Find_gcd_Extended(b % a, a, &x1, &y1);

    /*
      After recursive call, update the values
      of x and y
    */
    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}

// Driver Code
int main()
{
    int a = 5, m = 7;

    // Function call
    cout<<"The value of x is: ";
    Find_mod_Inverse(a, m);
    return 0;
}

 

Output:

The value of x is: 3

 

Time Complexity: O(log m)

The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.

Space complexity: O(1)

As constant space is used, the space complexity is O(1).
 

Iterative Approach using Extended Euclid’s Algorithm:

The idea is very similar as we applied for the recursive way of the modular multiplicative inverse. Just the difference lies in the implementation part, in the above example we applied a recursive approach, now we will be looking for the iterative approach.

Implementation in C++:

 

/*
  Iterative implementation for modular
  multiplicative inverse using Extended
  Euclid Algorithm
*/
#include <bits/stdc++.h>
using namespace std;

/*
  Function that returns modular inverse of a 
  under m using extended Euclid Algorithm
  Assuming: a and m are coprimes and 
  gcd(a, m) = 1
*/
int find_mod_Inverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;

if (m == 1)
{
    return 0;
}

while (a > 1) {


int quotient = a / m;
int t = m;

/*
  As m is the remainder, perform the same
  process as in Euclid's algo
*/
m = a % m, a = t;
t = y;

// Update y and x
y = x - quotient * y;
x = t;
}

/*
  Checking if x is negative. If it is
  then make it positive
*/
if (x < 0)
{
x += m0;
}

return x;
}

// Driver Code
int main()
{
int a = 5, m = 7;

// Function call
cout << "The value of x is: "<< find_mod_Inverse(a, m);
return 0;
}

 

 

Output:

The value of x is: 3

Time Complexity: O(log m)

The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.

Space Complexity: O(1)

As constant space is used, the space complexity is O(1).

 

III: Fermat’s little theorem approach:

This approach is based on Fermat’s little theorem. This approach can only work if m is prime. 


<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><msup><mi>a</mi><mrow><mi>m</mi><mo>-</mo><mn>1</mn></mrow></msup><mo>&#x2245;</mo><mn>1</mn><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi></mrow></mfenced></mrow></mstyle></math>

Multiplying by a-1on both sides we get, 


<math xmlns="http://www.w3.org/1998/Math/MathML"><mstyle mathsize="22px"><mrow><msup><mi>a</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>&#x2245;</mo><msup><mi>a</mi><mrow><mi>m</mi><mo>-</mo><mn>2</mn></mrow></msup><mfenced><mrow><mi>m</mi><mi>o</mi><mi>d</mi><mo>&#xA0;</mo><mi>m</mi></mrow></mfenced></mrow></mstyle></math>
 

/*
  C++ program for modular multiplicative 
  inverse when m is prime
*/
#include <iostream>
using namespace std;

/*
  Function to find gcd 
  of a and b
*/
int __gcd(int a, int b);

/*
  Function for computing the expression
  x raised to power y under modulo m
*/
int find_power(int x, int y, int m);

/*
  For prime m,this function finds modular inverse
  of a under modulo m
*/
void find_mod_Inverse(int a, int m)
{
    int g = __gcd(a, m);
    if (g != 1)
    {
        cout << "Inverse doesn't exist";
    }
    else
    {
        /*
          When a and m are prime, then modulo inverse
          can be defined as a^(m-2) mode m
        */
        cout << "The value of x is: "
            << find_power(a, m - 2, m);
    }
}

/*
  Function to compute x^y under
  modulo m
*/
int find_power(int x, int y, int m)
{
    if (y == 0)
    {
        return 1;
    }
    int p = find_power(x, y / 2, m) % m;
    p = (p * p) % m;

    return (y % 2 == 0) ? p : (x * p) % m;
}

// Function to return gcd of a and b
int __gcd(int x, int y)
{
    if (x == 0)
    {
        return y;
    }
    return __gcd(y % x, x);
}

// Driver code
int main()
{
    int a = 5, m = 7;

    // Function call
    find_mod_Inverse(a, m);
    return 0;
}

 

Output:

The value of x is: 3

 

Time Complexity: O(log m)

The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.

Space Complexity: O(1)

As constant space is used, space complexity for this approach is O(1).

Frequently Asked Questions:

What is the output of 3 mod 11?

The output of 3 mod 11 is 3.

What is an inverse?

The inverse is a way of representing a number in such a way that, when multiplied with its inverse, it gives 1 as result.

Eg: 5 X 1 / 5 = 1.

How do you do modular multiplicative inverse?

The modular multiplicative inverse is done by the “Chinese remainder theorem”. According to the Chinese remainder theorem, if one knows the remainder of the Euclidean division of an integer ’n’, then the remainder of the division of ‘n’ by the product of the integers can be uniquely determined under the condition that divisors are pairwise coprime

What is the easiest way to find a multiplicative inverse?

For any natural number x(0, 1, 2, 3, …), the multiplicative inverse is 1/x. For example, the multiplicative inverse of 7 is 1/7.

Key Takeaways:

In this article we learned about modular multiplicative inverse and various approaches to solving it, starting from the naive to efficient approach. But this isn’t the end.

You can also try solving problems on CodeStudio. If you think that this blog helped you, then share it with your friends!.
 

~ Pradipta Choudhury

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think