Modular Multiplicative Inverse

Brute Force Approach

We'll check for all numbers in the range [1, m-1] for a possible candidate that satisfies the equation ax % m = 1 and returns it. If no such candidate exists, we can conclude that a and m have a common factor and thus, there doesn't exist a valid modular multiplicative inverse, and we return -1.

Pseudocode

func brute(a, m):
	for all i from 1 to m - 1:
		if (a * i) % m == 1:
			return i
	return -1
	
brute(10, 499)

Code in C++

#include <bits/stdc++.h>
using namespace std;

// uncomment if needed
// #define int long long

int modular_multiplicative_inverse(int a, int MOD = 1e9 + 7){
    
    a = a % MOD;
    for(int i = 1; i <= MOD-1; i++){
        if((a * i) % MOD == 1){
            return i;
        }
    }
    return -1;
}

int32_t main(){
    int a = 10, MOD = 499;
    cout << modular_multiplicative_inverse(a, MOD);
}

Output

50

Time Complexity

O(m) time is consumed, as we loop and check the condition (ax % m == 1) for all m-1 possible candidates.

Space Complexity

O(1) extra space is consumed by the algorithm.

Optimized Extended-Euclidean Algorithm Approach

We can use the extended euclidean algorithm (if this topic is new for you, refer to the article here) to find the modular multiplicative inverse. We can use the below observations to arrive at the use of the extended euclidean algorithm in this case.

=> ax % m = 1

=> ax = 1 + mz, here z is a positive integer

=> ax - mz = 1

=> ax + my = 1, replace y = -z

We observe that, extended euclidean algorithm can find x, y, gcd(a, m) in the below equation

=> ax + my = gcd(a, m)

Also, notice that for modular multiplicative inverse to exist, the gcd(a, m) must be 1.

Hence, we can directly use the extended euclidean algorithm, and the x value obtained will be the modular multiplicative inverse of 'a (mod m)'.

The steps followed in the code:

1. We pass a and m into the extended euclidean algorithm function.
2. We obtain a gcd and associated values of x and y.
3. If the gcd is 1, we handle the case when x is negative (adding m to it and finding its modulus with m, adding m and taking modulus with m doesn't affect the result) and return x as the modular inverse.
4. If the gcd is not 1, we conclude there's no valid modular multiplicative inverse and return -1.
5. We print the result returned in either step 3 or 4.

Pseudocode

func extended_euc(a, b):
	if a equals 0: 
		return (b, 0, 1)
	[d, x1, y1] = extended_euc(b % a, a)
	y = y1 - x1 * (b / a)
	x = x1
	return d, x, y

[gcd, x, y] = extended_euc(10, 499)
if gcd equals 1:
	x = (x % m + m) % m
	print(x)
else:
	print(-1)

Code in C++

#include <bits/stdc++.h>
using namespace std;

// uncomment if needed
// #define int long long

int extended_euclidean(int a, int b, int& x, int& y) {
    if (!a) {
        // if a is 0, return
        x = 0, y = 1;
        return b;
    }
    int x1, y1;
    int d = extended_euclidean(b % a, a, x1, y1);
    x = y1 - x1 * (b / a);
    y = x1;
    return d;
}

int modular_multiplicative_inverse(int a, int m){
    int x, y;
    int gcd_a_and_m = extended_euclidean(a, m, x, y);
    
    // if the gcd is 1, the multiplicative modular inverse exists
    if(gcd_a_and_m == 1){
        // handle the case when x < 0
        x = (x % m + m) % m;
        return x;
    }
    return -1;
}

int32_t main(){
    int a = 10, MOD = 499;
    cout << modular_multiplicative_inverse(a, MOD);
}

Output

50

Time Complexity

The algorithm takes O(log₂(m)) time, same as the extended euclidean algorithm for any given input.

Space Complexity

O(1) extra space is needed, but O(log₂(m)) stack memory is consumed due to recursion.

Case-Specific Euler's Theorem Approach

Euler's theorem states that a^phi(m) ≡ 1(mod m) (here, phi(m) is the Euler's totient function). In the special case when m is prime, Euler's totient function phi(m)=m-1, and Euler's theorem becomes the popularly known Fermat's little theorem, a^m-1 ≡ 1(mod m).

We can rearrange the equations to obtain the below,

a^phi(m)-1 ≡ a^-1 (mod m), Here a^-1 is the modular multiplicative inverse.

Or, in the special case when m is prime, we obtain a^m-2 ≡ a^-1 (mod m).

We'll cover the code for when m is a prime number, as it's harder and time-consuming to calculate the Euler's totient function for a more generalised m.

In the code, we only have one step, where we calculate (a^m-2) % m using modular exponentiation when m is prime.

Pseudocode

// returns a^b mod(MOD) (a to the power b mod MOD)
func modular_exponentiation(a, b, MOD)
	ans = 1
	a = a mod(MOD)
	while b is more than 0
		if b is an odd number
			ans = (ans * a) mod(MOD)
		a = (a * a) mod(MOD)
		b = b / 2
	return ans

// it’s assumed that input m is a prime number
print(modular_exponentiation(a, m-2, m))

Code in C++

#include <bits/stdc++.h>
using namespace std;

// uncomment if needed
// #define int long long

int modular_exponentiation(int a, int b, int MOD = 1e9 + 7){
    int ans = 1;
    a = a % MOD;
    while(b > 0){
        if(b % 2 == 1){
            ans = (ans * a) % MOD;
        }
        a = (a * a) % MOD;
        b = b / 2;
    }
    return ans;
}

int modular_multiplicative_inverse(int a, int m){
    return modular_exponentiation(a, m-2, m);
}

int32_t main(){
    int a = 10, MOD = 499;
    cout << modular_multiplicative_inverse(a, MOD);
}

Output

50

Time Complexity

O(log₂(m)) time is taken by this algorithm when m is prime, similar to the extended euclidean algorithm solution. However, this method can be easily used with modular exponentiation and is slightly easier and faster to code iteratively in various circumstances (such as an interview or a contest).

Space Complexity

The algorithm consumes O(1) extra space.

Frequently Asked Questions

What is Modular Multiplicative Inverse?

The modular multiplicative inverse of a (mod m) is the number x, such ax ≡ 1 mod(m) (this essentially means m | ax - 1 (read as, `m divides a*x - 1`) or ax % m = 1. The modular inverse only exists if a and m are co-prime.

How do you find the modular multiplicative inverse?

The modular multiplicative inverse of a number is A X ≅ 1 (mod M). To find the modular multiplicative of a number, we put the values in the above formula. The value of X should fall in the range of 1, 2,... M-1.

What is an example of modular inverse?

An example of modular inverse includes: suppose the value of a is 3 and m is 7. Here a is an integer, and m is a positive integer. The x number that makes a * x mod m = 1 is the modular inverse of A mod C. In the example, the value of x will be 5. Because taking other values will not satisfy the modular value. 

What is the multiplicative inverse of 3 modulo 7?

a=3 and m=7, a is an integer, and m is a positive integer. gcd(3,7)= 1, the inverse exists.
(a*x) % m=1, x is an integer that lies in the range [1, m-1]
3*5 % 7=1 , 5 is the value for which the mod comes 1. Taking other values like 1,2,3,4.....will not satisfy the conditions.  For example, if we take x as 1, the value will be 3, which is not the required answer. So, the answer is 5.

What is the multiplicative inverse of 2 mod 7?

a=2 and m=7, a is an integer, and m is a positive integer. gcd(2,7)= 1, the inverse exists.
(a*x) % m=1, x is an integer that lies in the range [1, m-1]
2*4 % 7=1, 4 is the value for which the mod comes 1. Taking other values like 1,2,3,5.....will not satisfy the conditions.  For example, if we take x as 2, the value will be 4, which is not the required answer. So, the answer is 4.

Conclusion

This article teaches about modular multiplicative inverse and familiarizes you with the idea. We covered various approaches that hope to help you when you encounter a real scenario where you may need to use it to solve a problem quickly. You must check out  Number Theory which covers all the concepts on number theory you need to know to ace problem-solving.

Learn more about the C++ STL library if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.

Happy learning!