Modular Multiplicative Inverse

68.8k
0

Given two integers A and M, find the modular multiplicative inverse of A under modulo M. Return an integer X such that: (A * X) % M = 1 If no such value exists, return -1.

Example 1

Input: A = 3, M = 11

Output: 4

Explanation: 3 * 4 = 12, and 12 % 11 = 1.
So, 4 is the modular inverse of 3 under modulo 11.

Example 2

Input: A = 2, M = 6

Output: -1

Explanation: There is no number X such that (2 * X) % 6 = 1.
So, the modular inverse does not exist.

Brute Force Approach

The definition says that the answer is a number X for which: (A * X) % M = 1 So the most direct idea is to try every possible value of X. Since modular answers repeat after M, only values from 1 to M - 1 need to be checked. If any value satisfies the condition, that value is the inverse. If no value works, the inverse does not exist.

Algorithm

  • First, reduce A under modulo M so large values of A are brought into the useful range.

  • Try every possible value X from 1 to M - 1, because valid modular inverse values live inside this range.

  • For every X, check whether (A * X) % M becomes 1. This directly tests the definition of modular inverse.

  • If such an X is found, return it immediately because the required inverse has been found.

  • If the loop finishes without finding any value, return -1 because no modular inverse exists.

Dry Run

Modular Multiplicative Inverse Brute Dry Run

Modular Multiplicative Inverse Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Finds the modular inverse by checking every
possible value from 1 to M - 1.
*/
long long modInverse(long long A, long long M) {
/*
A modulus less than or equal to 1 cannot
give a valid inverse range.
*/
if (M <= 1) {
return -1;
}
/*
This keeps A inside the standard modulo range,
even when A is larger than M.
*/
A = ((A % M) + M) % M;
for (long long X = 1; X < M; X++) {
/*
This condition directly checks whether X
satisfies the modular inverse definition.
*/
if ((A * X) % M == 1) {
return X;
}
}
return -1;
}
};
// Driver code starts
int main() {
Solution sol;
long long A = 3;
long long M = 11;
cout << sol.modInverse(A, M);
return 0;
}

Complexity Analysis

Time Complexity: O(M), because all values from 1 to M - 1 may be checked.

Space Complexity: O(1), because constant space is used.

Better Approach

The modular inverse exists only when A and M are coprime, meaning: gcd(A, M) = 1 The Extended Euclidean Algorithm helps because it finds integers x and y such that: A * x + M * y = gcd(A, M) If gcd(A, M) = 1, then: A * x + M * y = 1

Now take modulo M on both sides. The M * y part becomes 0 under modulo M, so: A * x ≡ 1 (mod M) That means x is the modular inverse. Sometimes x may be negative, so it is normalized using modulo.

Algorithm

  • First, check whether M is valid. A modulus less than or equal to 1 cannot give a useful inverse range.

  • Reduce A under modulo M so the algorithm works with the standard remainder form.

  • Run the Extended Euclidean Algorithm on A and M. This gives gcd(A, M) and also the coefficient of A.

  • If the gcd is not 1, return -1 because the inverse exists only for coprime numbers.

  • Otherwise, normalize the coefficient of A into the range [0, M - 1]. This is done because Extended Euclid may return a negative coefficient, but modular answers are usually written as non-negative remainders.

Dry Run

Modular Multiplicative Inverse Better Dry Run

Modular Multiplicative Inverse Better Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Finds gcd(a, b) and coefficients x, y such that
a * x + b * y = gcd(a, b).
*/
long long extendedGcd(long long a, long long b, long long &x, long long &y) {
/*
When b becomes 0, gcd is a and the coefficient
of a is 1.
*/
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long x1;
long long y1;
long long gcdValue = extendedGcd(b, a % b, x1, y1);
/*
These assignments rebuild the coefficients while
returning from recursion.
*/
x = y1;
y = x1 - (a / b) * y1;
return gcdValue;
}
/*
Finds the modular inverse using Extended Euclidean
Algorithm for any valid coprime A and M.
*/
long long modInverse(long long A, long long M) {
/*
A modulus less than or equal to 1 cannot
give a valid inverse range.
*/
if (M <= 1) {
return -1;
}
/*
This keeps A inside the standard modulo range.
*/
A = ((A % M) + M) % M;
long long x;
long long y;
long long gcdValue = extendedGcd(A, M, x, y);
/*
If gcd is not 1, A and M are not coprime,
so the modular inverse does not exist.
*/
if (gcdValue != 1) {
return -1;
}
/*
x may be negative, so this converts it into
the standard modulo range.
*/
return ((x % M) + M) % M;
}
};
// Driver code starts
int main() {
Solution sol;
long long A = 3;
long long M = 11;
cout << sol.modInverse(A, M);
return 0;
}

Complexity Analysis

Time Complexity: O(log M), because the Euclidean algorithm reduces the numbers quickly.

Space Complexity: O(log M) for the recursive call stack.

Optimal Approach

This approach is used when M is prime. Fermat's Little Theorem says: A^(M - 1) ≡ 1 (mod M) when A is not divisible by prime M. Since the modular inverse of A is the value that turns A into 1 under multiplication, the formula becomes: A^(-1) ≡ A^(M - 2) (mod M)

So the answer is: pow(A, M - 2) % M The exponent can be huge, so binary exponentiation is used to calculate it quickly.

Algorithm

  • First, check whether M is valid. This approach assumes M is prime, so the caller should only use it in that case.

  • Reduce A under modulo M so values larger than M are handled correctly.

  • If A becomes 0, return -1 because 0 cannot have a modular inverse.

  • Use binary exponentiation to calculate A^(M - 2) % M. This is done because directly calculating the full power would be too large and slow.

  • Return the computed power as the modular inverse.

Dry Run

Modular Multiplicative Inverse Optimal Dry Run

Modular Multiplicative Inverse Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Computes base^power under modulo M using
binary exponentiation.
*/
long long powerMod(long long base, long long power, long long M) {
/*
result stores the answer built from the selected
powers of base.
*/
long long result = 1;
base = ((base % M) + M) % M;
while (power > 0) {
/*
If the current bit is set, this power of base
contributes to the final answer.
*/
if (power % 2 == 1) {
result = (result * base) % M;
}
/*
Squaring base prepares the next power of two.
*/
base = (base * base) % M;
power /= 2;
}
return result;
}
/*
Finds modular inverse using Fermat's Little Theorem.
This function assumes M is prime.
*/
long long modInverse(long long A, long long M) {
/*
A modulus less than or equal to 1 cannot
give a valid inverse range.
*/
if (M <= 1) {
return -1;
}
A = ((A % M) + M) % M;
/*
Under a prime modulus, only multiples of M
fail to have an inverse.
*/
if (A == 0) {
return -1;
}
return powerMod(A, M - 2, M);
}
};
// Driver code starts
int main() {
Solution sol;
long long A = 3;
long long M = 11;
cout << sol.modInverse(A, M);
return 0;
}

Complexity Analysis

Time Complexity: O(log M), because binary exponentiation halves the exponent at each step.

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

Because A * X must become 1 under modulo M. If A and M share a common factor greater than 1, then A * X will also keep sharing that factor, so it cannot become 1.

Maths

Read Similar Blogs

Two PointerSortingBinary SearchArraysMaths

Koko Eating Bananas: Find the Minimum Eating Speed

There are N piles of bananas, the i th pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k . Each hour, she chooses...

109k
Two PointerSortingMathsHeapBinary SearchArrays

Minimize Maximum Distance Between Gas Stations

You are given a sorted array representing the exact integer positions of several gas stations on a highway. You are also given an integer k, which represents the number of brand new gas stations yo...

120.4k
Two PointerSortingMathsBinary SearchArrays

Book Allocation Problem: Allocate Minimum Pages

Given an array pages , where pages[i] represents the number of pages in the i-th book, and an integer students , allocate all books among the students. The allocation must follow these rules: Each...

63.2k
Comments0