Given two integers A and M, find the modular multiplicative inverse of A under modulo M.
The modular multiplicative inverse is an integer X such that:
A X ≅ 1 (mod M)
Note: The value of X should be in the range {1, 2, … M-1}, i.e., in the range of integer modulo M. ( Note that X cannot be 0 as A*0 mod M will never be 1). The multiplicative inverse of “A modulo M” exists if and only if A and M are relatively prime (i.e. if gcd(A, M) = 1)
Examples:
Input: A = 3, M = 11
Output: 4
Explanation: Since (4*3) mod 11 = 1, 4 is modulo inverse of 3(under 11).
One might think, 15 also as a valid output as “(15*3) mod 11”
is also 1, but 15 is not in range {1, 2, … 10}, so not valid.Input: A = 10, M = 17
Output: 12
Explanation: Since (10*12) mod 17 = 1, 12 is modulo inverse of 10(under 17).
Naive Approach: To solve the problem, follow the below idea:
A naive method is to try all numbers from 1 to m. For every number x, check if (A * X) % M is 1
Below is the implementation of the above approach:
C++
// C++ program to find modular// inverse of A under modulo M#include <bits/stdc++.h>using namespace std;// A naive method to find modular// multiplicative inverse of 'A'// under modulo 'M'int modInverse(int A, int M){ for (int X = 1; X < M; X++) if (((A % M) * (X % M)) % M == 1) return X;}// Driver codeint main(){ int A = 3, M = 11; // Function call cout << modInverse(A, M); return 0;} |
Java
// Java program to find modular inverse// of A under modulo Mimport java.io.*;class GFG { // A naive method to find modulor // multiplicative inverse of A // under modulo M static int modInverse(int A, int M) { for (int X = 1; X < M; X++) if (((A % M) * (X % M)) % M == 1) return X; return 1; } // Driver Code public static void main(String args[]) { int A = 3, M = 11; // Function call System.out.println(modInverse(A, M)); }}/*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python3 program to find modular# inverse of A under modulo M# A naive method to find modulor# multiplicative inverse of A# under modulo Mdef modInverse(A, M): for X in range(1, M): if (((A % M) * (X % M)) % M == 1): return X return -1# Driver Codeif __name__ == "__main__": A = 3 M = 11 # Function call print(modInverse(A, M))# This code is contributed by Nikita Tiwari. |
C#
// C# program to find modular inverse// of A under modulo Musing System;class GFG { // A naive method to find modulor // multiplicative inverse of A // under modulo M static int modInverse(int A, int M) { for (int X = 1; X < M; X++) if (((A % M) * (X % M)) % M == 1) return X; return 1; } // Driver Code public static void Main() { int A = 3, M = 11; // Function call Console.WriteLine(modInverse(A, M)); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP program to find modular // inverse of A under modulo M// A naive method to find modulor// multiplicative inverse of// A under modulo Mfunction modInverse( $A, $M){ for ($X = 1; $X < $M; $X++) if ((($A%$M) * ($X%$M)) % $M == 1) return $X;}// Driver Code$A = 3; $M = 11;// Function callecho modInverse($A, $M);// This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to find modular // inverse of a under modulo m// A naive method to find modulor// multiplicative inverse of// 'a' under modulo 'm'function modInverse(a, m){ for(let x = 1; x < m; x++) if (((a % m) * (x % m)) % m == 1) return x;}// Driver Codelet a = 3; let m = 11;// Function calldocument.write(modInverse(a, m));// This code is contributed by _saurabh_jaiswal.</script> |
Output
4
Time Complexity: O(M)
Auxiliary Space: O(1)
Modular multiplicative inverse when M and A are coprime or gcd(A, M)=1:
The idea is to use Extended Euclidean algorithms that take two integers ‘a’ and ‘b’, then find their gcd, and also find ‘x’ and ‘y’ such that
ax + by = 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.
Ax + My = 1
If we take modulo M on both sides, we get
Ax + My ≅ 1 (mod M)
We can remove the second term on left side as ‘My (mod M)’ would always be 0 for an integer y.
Ax ≅ 1 (mod M)
So the ‘x’ that we can find using Extended Euclid Algorithm is the multiplicative inverse of ‘A’
Below is the implementation of the above approach:
C++
// C++ program to find multiplicative modulo// inverse using Extended Euclid algorithm.#include <bits/stdc++.h>using namespace std;// Function for extended Euclidean Algorithmint gcdExtended(int a, int b, int* x, int* y);// Function to find modulo inverse of avoid modInverse(int A, int M){ int x, y; int g = gcdExtended(A, M, &x, &y); if (g != 1) cout << "Inverse doesn't exist"; else { // m is added to handle negative x int res = (x % M + M) % M; cout << "Modular multiplicative inverse is " << res; }}// Function for extended Euclidean Algorithmint gcdExtended(int a, int b, int* x, int* y){ // Base Case if (a == 0) { *x = 0, *y = 1; return b; } // To store results of recursive call int x1, y1; int gcd = gcdExtended(b % a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b / a) * x1; *y = x1; return gcd;}// Driver Codeint main(){ int A = 3, M = 11; // Function call modInverse(A, M); return 0;}// This code is contributed by khushboogoyal499 |
C
// C program to find multiplicative modulo inverse using// Extended Euclid algorithm.#include <stdio.h>// C function for extended Euclidean Algorithmint gcdExtended(int a, int b, int* x, int* y);// Function to find modulo inverse of avoid modInverse(int A, int M){ int x, y; int g = gcdExtended(A, M, &x, &y); if (g != 1) printf("Inverse doesn't exist"); else { // m is added to handle negative x int res = (x % M + M) % M; printf("Modular multiplicative inverse is %d", res); }}// C function for extended Euclidean Algorithmint gcdExtended(int a, int b, int* x, int* y){ // Base Case if (a == 0) { *x = 0, *y = 1; return b; } int x1, y1; // To store results of recursive call int gcd = gcdExtended(b % a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b / a) * x1; *y = x1; return gcd;}// Driver Codeint main(){ int A = 3, M = 11; // Function call modInverse(A, M); return 0;} |
Java
// java program to find multiplicative modulo// inverse using Extended Euclid algorithm.public class GFG { // Global Variables public static int x; public static int y; // Function for extended Euclidean Algorithm static int gcdExtended(int a, int b) { // Base Case if (a == 0) { x = 0; y = 1; return b; } // To store results of recursive call int gcd = gcdExtended(b % a, a); int x1 = x; int y1 = y; // Update x and y using results of recursive // call int tmp = b / a; x = y1 - tmp * x1; y = x1; return gcd; } static void modInverse(int A, int M) { int g = gcdExtended(A, M); if (g != 1) { System.out.println("Inverse doesn't exist"); } else { // m is added to handle negative x int res = (x % M + M) % M; System.out.println( "Modular multiplicative inverse is " + res); } } // Driver code public static void main(String[] args) { int A = 3, M = 11; // Function Call modInverse(A, M); }}// The code is contributed by Gautam goel (gautamgoel962) |
Python3
# Python3 program to find multiplicative modulo# inverse using Extended Euclid algorithm.# Global Variablesx, y = 0, 1# Function for extended Euclidean Algorithmdef gcdExtended(a, b): global x, y # Base Case if (a == 0): x = 0 y = 1 return b # To store results of recursive call gcd = gcdExtended(b % a, a) x1 = x y1 = y # Update x and y using results of recursive # call x = y1 - (b // a) * x1 y = x1 return gcddef modInverse(A, M): g = gcdExtended(A, M) if (g != 1): print("Inverse doesn't exist") else: # m is added to handle negative x res = (x % M + M) % M print("Modular multiplicative inverse is ", res)# Driver Codeif __name__ == "__main__": A = 3 M = 11 # Function call modInverse(A, M)# This code is contributed by phasing17 |
C#
// C# program to find multiplicative modulo// inverse using Extended Euclid algorithm.using System;public class GFG { public static int x, y; // Function for extended Euclidean Algorithm static int gcdExtended(int a, int b) { // Base Case if (a == 0) { x = 0; y = 1; return b; } // To store results of recursive call int gcd = gcdExtended(b % a, a); int x1 = x; int y1 = y; // Update x and y using results of recursive // call x = y1 - (b / a) * x1; y = x1; return gcd; } // Function to find modulo inverse of a static void modInverse(int A, int M) { int g = gcdExtended(A, M); if (g != 1) Console.Write("Inverse doesn't exist"); else { // M is added to handle negative x int res = (x % M + M) % M; Console.Write( "Modular multiplicative inverse is " + res); } } // Driver Code public static void Main(string[] args) { int A = 3, M = 11; // Function call modInverse(A, M); }}// this code is contributed by phasing17 |
PHP
<?php// PHP program to find multiplicative modulo // inverse using Extended Euclid algorithm.// Function to find modulo inverse of afunction modInverse($A, $M){ $x = 0; $y = 0; $g = gcdExtended($A, $M, $x, $y); if ($g != 1) echo "Inverse doesn't exist"; else { // m is added to handle negative x $res = ($x % $M + $M) % $M; echo "Modular multiplicative " . "inverse is " . $res; }}// function for extended Euclidean Algorithmfunction gcdExtended($a, $b, &$x, &$y){ // Base Case if ($a == 0) { $x = 0; $y = 1; return $b; } $x1; $y1; // To store results of recursive call $gcd = gcdExtended($b%$a, $a, $x1, $y1); // Update x and y using results of // recursive call $x = $y1 - (int)($b/$a) * $x1; $y = $x1; return $gcd;}// Driver Code$A = 3;$M = 11;// Function callmodInverse($A, $M);// This code is contributed by chandan_jnu?> |
Javascript
<script>// JavaScript program to find multiplicative modulo// inverse using Extended Euclid algorithm.// Global Variableslet x, y;// Function for extended Euclidean Algorithmfunction gcdExtended(a, b){ // Base Case if (a == 0) { x = 0; y = 1; return b; } // To store results of recursive call let gcd = gcdExtended(b % a, a); let x1 = x; let y1 = y; // Update x and y using results of recursive // call x = y1 - Math.floor(b / a) * x1; y = x1; return gcd;}function modInverse(a, m){ let g = gcdExtended(a, m); if (g != 1){ document.write("Inverse doesn't exist"); } else{ // m is added to handle negative x let res = (x % m + m) % m; document.write("Modular multiplicative inverse is ", res); }}// Driver Code{ let a = 3, m = 11; // Function call modInverse(a, m);} // This code is contributed by Gautam goel (gautamgoel962)</script> |
Output
Modular multiplicative inverse is 4
Time Complexity: O(log M)
Auxiliary Space: O(log M), because of the internal recursion stack.
Iterative Implementation of the above approach:
C++
// Iterative C++ program to find modular// inverse using extended Euclid algorithm#include <bits/stdc++.h>using namespace std;// Returns modulo inverse of a with respect// to m using extended Euclid Algorithm// Assumption: a and m are coprimes, i.e.,// gcd(A, M) = 1int modInverse(int A, int M){ int m0 = M; int y = 0, x = 1; if (M == 1) return 0; while (A > 1) { // q is quotient int q = A / M; int t = M; // m is remainder now, process same as // Euclid's algo M = A % M, A = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x;}// Driver Codeint main(){ int A = 3, M = 11; // Function call cout << "Modular multiplicative inverse is " << modInverse(A, M); return 0;}// this code is contributed by shivanisinghss2110 |
C
// Iterative C program to find modular// inverse using extended Euclid algorithm#include <stdio.h>// Returns modulo inverse of a with respect// to m using extended Euclid Algorithm// Assumption: a and m are coprimes, i.e.,// gcd(A, M) = 1int modInverse(int A, int M){ int m0 = M; int y = 0, x = 1; if (M == 1) return 0; while (A > 1) { // q is quotient int q = A / M; int t = M; // m is remainder now, process same as // Euclid's algo M = A % M, A = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x;}// Driver Codeint main(){ int A = 3, M = 11; // Function call printf("Modular multiplicative inverse is %d\n", modInverse(A, M)); return 0;} |
Java
// Iterative Java program to find modular// inverse using extended Euclid algorithmclass GFG { // Returns modulo inverse of a with // respect to m using extended Euclid // Algorithm Assumption: a and m are // coprimes, i.e., gcd(A, M) = 1 static int modInverse(int A, int M) { int m0 = M; int y = 0, x = 1; if (M == 1) return 0; while (A > 1) { // q is quotient int q = A / M; int t = M; // m is remainder now, process // same as Euclid's algo M = A % M; A = t; t = y; // Update x and y y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } // Driver code public static void main(String args[]) { int A = 3, M = 11; // Function call System.out.println("Modular multiplicative " + "inverse is " + modInverse(A, M)); }}/*This code is contributed by Nikita Tiwari.*/ |
Python3
# Iterative Python 3 program to find# modular inverse using extended# Euclid algorithm# Returns modulo inverse of a with# respect to m using extended Euclid# Algorithm Assumption: a and m are# coprimes, i.e., gcd(A, M) = 1def modInverse(A, M): m0 = M y = 0 x = 1 if (M == 1): return 0 while (A > 1): # q is quotient q = A // M t = M # m is remainder now, process # same as Euclid's algo M = A % M A = t t = y # Update x and y y = x - q * y x = t # Make x positive if (x < 0): x = x + m0 return x# Driver codeif __name__ == "__main__": A = 3 M = 11 # Function call print("Modular multiplicative inverse is", modInverse(A, M))# This code is contributed by Nikita tiwari. |
C#
// Iterative C# program to find modular// inverse using extended Euclid algorithmusing System;class GFG { // Returns modulo inverse of a with // respect to m using extended Euclid // Algorithm Assumption: a and m are // coprimes, i.e., gcd(A, M) = 1 static int modInverse(int A, int M) { int m0 = M; int y = 0, x = 1; if (M == 1) return 0; while (A > 1) { // q is quotient int q = A / M; int t = M; // m is remainder now, process // same as Euclid's algo M = A % M; A = t; t = y; // Update x and y y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } // Driver Code public static void Main() { int A = 3, M = 11; // Function call Console.WriteLine("Modular multiplicative " + "inverse is " + modInverse(A, M)); }}// This code is contributed by anuj_67. |
PHP
<?php// Iterative PHP program to find modular// inverse using extended Euclid algorithm// Returns modulo inverse of a with respect// to m using extended Euclid Algorithm// Assumption: a and m are coprimes, i.e.,// gcd(a, m) = 1function modInverse($A, $M){ $m0 = $M; $y = 0; $x = 1; if ($m == 1) return 0; while ($A > 1) { // q is quotient $q = (int) ($A / $M); $t = $M; // m is remainder now, // process same as // Euclid's algo $M = $A % $M; $A = $t; $t = $y; // Update y and x $y = $x - $q * $y; $x = $t; } // Make x positive if ($x < 0) $x += $m0; return $x;} // Driver Code $A = 3; $M = 11; // Function call echo "Modular multiplicative inverse is: ", modInverse($A, $M); // This code is contributed by Anuj_67?> |
Javascript
<script>// Iterative Javascript program to find modular// inverse using extended Euclid algorithm// Returns modulo inverse of a with respect// to m using extended Euclid Algorithm// Assumption: a and m are coprimes, i.e.,// gcd(a, m) = 1function modInverse(a, m){ let m0 = m; let y = 0; let x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient let q = parseInt(a / m); let t = m; // m is remainder now, // process same as // Euclid's algo m = a % m; a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x;}// Driver Codelet a = 3;let m = 11;// Function calldocument.write(`Modular multiplicative inverse is ${modInverse(a, m)}`); // This code is contributed by _saurabh_jaiswal</script> |
Output
Modular multiplicative inverse is 4
Time Complexity: O(log m)
Auxiliary Space: O(1)
Modular multiplicative inverse when M is prime:
If we know M is prime, then we can also use Fermat’s little theorem to find the inverse.
aM-1 ≅ 1 (mod M)
If we multiply both sides with a-1, we get
a-1 ≅ a M-2 (mod M)
Below is the implementation of the above approach:
C++
// C++ program to find modular inverse of A under modulo M// This program works only if M is prime.#include <bits/stdc++.h>using namespace std;// To find GCD of a and bint gcd(int a, int b);// To compute x raised to power y under modulo Mint power(int x, unsigned int y, unsigned int M);// Function to find modular inverse of a under modulo M// Assumption: M is primevoid modInverse(int A, int M){ int g = gcd(A, M); if (g != 1) cout << "Inverse doesn't exist"; else { // If a and m are relatively prime, then modulo // inverse is a^(m-2) mode m cout << "Modular multiplicative inverse is " << power(A, M - 2, M); }}// To compute x^y under modulo mint power(int x, unsigned int y, unsigned int M){ if (y == 0) return 1; int p = 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 bint gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Driver codeint main(){ int A = 3, M = 11; // Function call modInverse(A, M); return 0;} |
Java
// Java program to find modular// inverse of A under modulo M// This program works only if// M is prime.import java.io.*;class GFG { // Function to find modular inverse of a // under modulo M Assumption: M is prime static void modInverse(int A, int M) { int g = gcd(A, M); if (g != 1) System.out.println("Inverse doesn't exist"); else { // If a and m are relatively prime, then modulo // inverse is a^(m-2) mode m System.out.println( "Modular multiplicative inverse is " + power(A, M - 2, M)); } } static int power(int x, int y, int M) { if (y == 0) return 1; int p = power(x, y / 2, M) % M; p = (int)((p * (long)p) % M); if (y % 2 == 0) return p; else return (int)((x * (long)p) % M); } // Function to return gcd of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Driver Code public static void main(String args[]) { int A = 3, M = 11; // Function call modInverse(A, M); }}// This code is contributed by Nikita Tiwari. |
Python3
# Python3 program to find modular# inverse of A under modulo M# This program works only if M is prime.# Function to find modular# inverse of A under modulo M# Assumption: M is primedef modInverse(A, M): g = gcd(A, M) if (g != 1): print("Inverse doesn't exist") else: # If A and M are relatively prime, # then modulo inverse is A^(M-2) mod M print("Modular multiplicative inverse is ", power(A, M - 2, M))# To compute x^y under modulo Mdef power(x, y, M): if (y == 0): return 1 p = power(x, y // 2, M) % M p = (p * p) % M if(y % 2 == 0): return p else: return ((x * p) % M)# Function to return gcd of a and bdef gcd(a, b): if (a == 0): return b return gcd(b % a, a)# Driver Codeif __name__ == "__main__": A = 3 M = 11 # Function call modInverse(A, M)# This code is contributed by Nikita Tiwari. |
C#
// C# program to find modular// inverse of a under modulo M// This program works only if// M is prime.using System;class GFG { // Function to find modular // inverse of A under modulo // M Assumption: M is prime static void modInverse(int A, int M) { int g = gcd(A, M); if (g != 1) Console.Write("Inverse doesn't exist"); else { // If A and M are relatively // prime, then modulo inverse // is A^(M-2) mod M Console.Write( "Modular multiplicative inverse is " + power(A, M - 2, M)); } } // To compute x^y under // modulo M static int power(int x, int y, int M) { if (y == 0) return 1; int p = power(x, y / 2, M) % M; p = (p * p) % M; if (y % 2 == 0) return p; else return (x * p) % M; } // Function to return // gcd of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Driver Code public static void Main() { int A = 3, M = 11; // Function call modInverse(A, M); }}// This code is contributed by nitin mittal. |
PHP
<?php// PHP program to find modular // inverse of A under modulo M// This program works only if M// is prime.// Function to find modular// inverse of A under modulo// M Assumption: M is primefunction modInverse( $A, $M){ $g = gcd($A, $M); if ($g != 1) echo "Inverse doesn't exist"; else { // If A and M are relatively // prime, then modulo inverse // is A^(M-2) mod M echo "Modular multiplicative inverse is " , power($A, $M - 2, $M); }}// To compute x^y under modulo mfunction power( $x, $y, $M){ if ($y == 0) return 1; $p = 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 bfunction gcd($a, $b){ if ($a == 0) return $b; return gcd($b % $a, $a);}// Driver Code$A = 3;$M = 11;// Function callmodInverse($A, $M); // This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to find modular inverse of a under modulo m// This program works only if m is prime.// Function to find modular inverse of a under modulo m// Assumption: m is primefunction modInverse(a, m){ let g = gcd(a, m); if (g != 1) document.write("Inverse doesn't exist"); else { // If a and m are relatively prime, then modulo // inverse is a^(m-2) mode m document.write("Modular multiplicative inverse is " + power(a, m - 2, m)); }}// To compute x^y under modulo mfunction power(x, y, m){ if (y == 0) return 1; let p = power(x, parseInt(y / 2), m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m;}// Function to return gcd of a and bfunction gcd(a, b){ if (a == 0) return b; return gcd(b % a, a);}// Driver codelet a = 3, m = 11;// Function callmodInverse(a, m);// This code is contributed by subham348.</script> |
Output
Modular multiplicative inverse is 4
Time Complexity: O(log M)
Auxiliary Space: O(log M), because of the internal recursion stack.
Applications:
Computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method.
This article is contributed by Ankur. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
