How to Calculate Modular Multiplicative Inverse in Python
 Calculate Modular Multiplicative Inverse Using the Naive Iterative Approach
 Calculate Modular Multiplicative Inverse Using Modular Exponentiation
 Calculate Modular Multiplicative Inverse Using the Extended Euclidean Algorithm
 Calculate Modular Multiplicative Inverse in Python Using Fermat’s Little Theorem
 Conclusion
The modular multiplicative inverse plays a crucial role in modular arithmetic, cryptography, and various mathematical applications. It is important to note that not all integers have a modular multiplicative inverse.
For the inverse to exist, a
and m
must be coprime, meaning their greatest common divisor (GCD) is equal to 1 (i.e., gcd(a, m) = 1
).
If a
and m
are not coprime, the modular multiplicative inverse does not exist for that pair. In such cases, it’s important to verify the coprimality of a
and m
before attempting to find the inverse.
In this article, we will explore how to calculate the modular multiplicative inverse in Python.
Calculate Modular Multiplicative Inverse Using the Naive Iterative Approach
The naive iterative approach to finding the modular multiplicative inverse is straightforward but not the most efficient method.
It involves checking each integer in the range [1, m1]
to see if it satisfies the condition (a * x) % m = 1
. This condition represents the definition of the modular multiplicative inverse.
Here’s a Python function that implements this approach:
def find_mod_inv(a, m):
for x in range(1, m):
if (a % m) * (x % m) % m == 1:
return x
raise Exception("The modular inverse does not exist.")
Let’s break down how this approach works step by step:

The method takes two integers as input:
a
andm
.a
is the number for which we want to find the modular multiplicative inverse under modulom
. We assume thata
andm
are positive integers andm
is greater than 1. 
The approach begins by setting up a loop that iterates over
x
within a specified range. This range is typically[1, m1]
, as the modular multiplicative inverse must be within this range.for x in range(1, m):

For each value of
x
, the approach checks whether the condition(a * x) % m = 1
is satisfied. Ifx
satisfies this condition, it means thatx
is the modular multiplicative inverse of the integera
under modulom
.(a * x)
calculates the product ofa
andx
.(a * x) % m
calculates the remainder when the product is divided bym
. If the remainder is
1
, it means thatx
is the modular multiplicative inverse of the integera
under modulom
.

If the condition is met for a particular
x
value, the function returnsx
as the modular multiplicative inverse.return x

If none of the
x
values within the specified range satisfy the condition(a * x) % m = 1
, the approach raises an exception. This indicates that the modular multiplicative inverse does not exist for the givena
andm
because they are not coprime (i.e.,gcd(a, m) != 1
).raise Exception("The modular inverse does not exist.")

The function returns the modular multiplicative inverse if it exists or raises an exception if it does not.
Let’s consider an example to find the modular multiplicative inverse of 13
under modulo 22
:
def find_mod_inv(a, m):
for x in range(1, m):
if (a % m) * (x % m) % m == 1:
return x
raise Exception("The modular inverse does not exist.")
a = 13
m = 22
try:
res = find_mod_inv(a, m)
print("The required modular inverse is: " + str(res))
except Exception as e:
print("The modular inverse does not exist.")
Output:
The required modular inverse is: 17
In this example, we successfully found that the modular multiplicative inverse of 13
under modulo 22
is 17
. This value satisfies the condition (13 * 17) % 22 = 1
.
Calculate Modular Multiplicative Inverse Using Modular Exponentiation
The Modular Exponentiation method is a powerful algorithm to find the modular multiplicative inverse efficiently, especially when working with large numbers. It is based on the properties of modular arithmetic and the concept of repeated squaring and multiplication.
Here’s how the Modular Exponentiation method works:

The method takes two integers as input 
a
andm
, wherea
is the number for which we want to find the modular multiplicative inverse, andm
is the modulo value. It is assumed that
a
andm
are positive integers, andm
is greater than 1.  Furthermore, it’s essential to ensure that
a
andm
are coprime (i.e.,gcd(a, m) = 1
).
 It is assumed that

Calculate
x
using the Modular Exponentiation method. The goal is to findx
such that(a * x) % m = 1
. To do this, we raise
a
to the power of1
modulom
. This is because(a^(1) % m)
yields the modular multiplicative inverse of the integera
under modulom
.  Mathematically, it can be expressed as:
x = (a^(1)) % m
.
 To do this, we raise

Return the result. The calculated value of
x
is the modular multiplicative inverse ofa
under modulom
.
Let’s implement the Modular Exponentiation method in Python:
def mod_inverse(a, m):
if math.gcd(a, m) != 1:
raise ValueError("Modular inverse does not exist")
return pow(a, 1, m)
In this implementation:

We check whether
a
andm
are coprime. If they are not, we raise an exception because the modular multiplicative inverse does not exist. 
We calculate
x
using thepow
function with exponent1
and modulom
.
Let’s find the modular multiplicative inverse of 13
under modulo 22
using the Modular Exponentiation method:
import math
def mod_inverse(a, m):
if math.gcd(a, m) != 1:
raise ValueError("Modular inverse does not exist")
return pow(a, 1, m)
a = 13
m = 22
try:
res = mod_inverse(a, m)
print("The required modular inverse is: " + str(res))
except ValueError as e:
print("The modular inverse does not exist.")
Output:
The required modular inverse is: 17
In this example, we successfully found that the modular multiplicative inverse of 13
under modulo 22
is 17
using the Modular Exponentiation method.
This method is efficient and suitable for both small and large values of a
and m
, provided they are coprime.
Calculate Modular Multiplicative Inverse Using the Extended Euclidean Algorithm
The Extended Euclidean Algorithm is another method for finding the modular multiplicative inverse efficiently. It is particularly useful when m
is a prime number, but it can also be used for any m
as long as a
and m
are coprime.
The algorithm works as follows:

The method takes two integers as input 
a
andm
, wherea
is the number for which we want to find the modular multiplicative inverse, andm
is the modulo value. It is assumed thata
andm
are positive integers, andm
is greater than 1. 
Use the Extended Euclidean Algorithm to calculate the GCD of
a
andm
(i.e.,gcd(a, m)
). If the GCD is not 1, it means that
a
andm
are not coprime, and the modular multiplicative inverse does not exist. In this case, the algorithm terminates.  If the GCD is 1, it means
a
andm
are coprime, and the algorithm proceeds to calculate the Bézout coefficientsx
andy
such thatax + my = 1
. These coefficients are essential to finding the modular multiplicative inverse.
 If the GCD is not 1, it means that

Return the result:
 The Bézout coefficients
x
andy
are calculated as part of the Extended Euclidean Algorithm. We are interested inx
because it is the modular multiplicative inverse.  The calculated
x
is returned as the modular multiplicative inverse ofa
under modulom
.
 The Bézout coefficients
Let’s implement the Extended Euclidean Algorithm in Python:
def extended_gcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = extended_gcd(b % a, a)
return (g, y  (b // a) * x, x)
def mod_inverse(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError("Modular inverse does not exist")
else:
return x % m
In this implementation:

The
extended_gcd
function calculates the GCD and Bézout coefficientsx
andy
using recursion. 
The
mod_inverse
function checks whethera
andm
are coprime. If they are, it calculatesx
and returns it as the modular multiplicative inverse.
Let’s find the modular multiplicative inverse of 13
under modulo 22
using the Extended Euclidean Algorithm:
def extended_gcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = extended_gcd(b % a, a)
return (g, y  (b // a) * x, x)
def mod_inverse(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError("Modular inverse does not exist")
else:
return x % m
a = 13
m = 22
try:
res = mod_inverse(a, m)
print("The required modular inverse is: " + str(res))
except ValueError as e:
print("The modular inverse does not exist.")
Output:
The required modular inverse is: 17
In this example, we successfully found that the modular multiplicative inverse of 13
under modulo 22
is 17
using the Extended Euclidean Algorithm.
Calculate Modular Multiplicative Inverse in Python Using Fermat’s Little Theorem
Fermat’s Little Theorem is a significant result in number theory that provides a way to find the modular multiplicative inverse. The theorem states that if the variable p
is a prime number and a
is an integer not divisible by p
, then:
In this equation, a
is the base, p
is the prime modulo, and p1
is the exponent.
To find the modular multiplicative inverse x
of a
under modulo m
, we can use Fermat’s Little Theorem if m
is prime and a
is not divisible by m
. The modular inverse can be calculated as follows:
This method is highly efficient when m
is prime, making it a valuable tool in cryptography and number theory.
Let’s implement the calculation of the modular multiplicative inverse using Fermat’s Little Theorem in Python:
def mod_inverse(a, m):
if is_prime(m):
if a < 1 or a >= m:
raise ValueError("Invalid input: 'a' must be in the range [1, m1]")
return pow(a, m  2, m)
else:
raise ValueError("Fermat's Little Theorem only applies when 'm' is prime.")
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
In this implementation:

The
mod_inverse
function first checks whetherm
is prime using theis_prime
function. Ifm
is prime anda
is within the valid range[1, m1]
, it calculatesx
using Fermat’s Little Theorem withpow(a, m  2, m)
. 
The
is_prime
function checks if a number is prime, ensuring that the method is only used whenm
is prime.
Let’s find the modular multiplicative inverse of 13
under modulo 17
using Fermat’s Little Theorem:
def mod_inverse(a, m):
if is_prime(m):
if a < 1 or a >= m:
raise ValueError("Invalid input: 'a' must be in the range [1, m1]")
return pow(a, m  2, m)
else:
raise ValueError("Fermat's Little Theorem only applies when 'm' is prime.")
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
a = 13
m = 17
try:
res = mod_inverse(a, m)
print("The required modular inverse is: " + str(res))
except ValueError as e:
print(e)
Output:
The required modular inverse is: 4
In this example, we successfully found that the modular multiplicative inverse of 13
under modulo 17
is 4
using Fermat’s Little Theorem.
Conclusion
In this article, we explored several methods for calculating the modular multiplicative inverse in Python, each with its advantages and use cases. These methods include the Naive Iterative Approach, Modular Exponentiation, the Extended Euclidean Algorithm, and Fermat’s Little Theorem.

The Naive Iterative Approach is a straightforward method that checks each integer within a specified range to find the modular inverse. While it may not be the most efficient, it provides a clear and simple way to solve the problem.

Modular Exponentiation offers an efficient algorithm, particularly suitable for large numbers. It leverages the principles of modular arithmetic and repeated squaring to find the inverse quickly.

The Extended Euclidean Algorithm is a powerful method, especially when the modulo
m
is prime. It efficiently calculates the modular multiplicative inverse by determining the GCD and Bézout coefficients, ensuring thata
andm
are coprime. 
Fermat’s Little Theorem is a valuable tool when
m
is prime anda
is not divisible bym
. It provides an efficient and elegant solution to the problem by raisinga
to the power ofm2
modulom
.
In practice, the choice of method depends on factors such as the size of the numbers, the properties of a
and m
, and the computational resources available. By understanding and applying these methods, you can confidently tackle modular multiplicative inverse problems in Python and apply them to a wide array of mathematical and cryptographic challenges.
Suraj Joshi is a backend software engineer at Matrice.ai.
LinkedIn