Inverse Modulo Calculator
Table of contents
Modulo congruenceWhat is inverse modulo?How to find the modular inverse?How to use this inverse modulo calculator?FAQsWelcome to the inverse modulo calculator! It's here to help you whenever you need to determine modular multiplicative inverses or modular additive inverses.
If you're unsure what the inverse modulo is, scroll down! We will give you all the necessary definitions and teach you how to find the modular inverse by hand!
Modulo congruence
Before we learn what inverse modulo is, we need to get familiar with the congruence relation.
Let n
be a natural number (nonzero). Two integers a
and b
are said to be congruent modulo n
if they both have the same remainder when divided by n
. Equivalently, the situation is the same when the difference a  b
is divisible by n
with zero as a remainder, i.e., if a  b
is a multiple of n
.
We denote the fact that a
and b
are congruent modulo n
by:
a ≡ b (mod n)
.
Let's take a look at two examples.

Example 1.
14
and99
are congruent modulo5
:14 ≡ 99 (mod 5)
because
99  14 = 85
and85
is a multiple of5
. Equivalently, we see that14
and99
have the same remainder when divided by5
:14 mod 5 = 4
99 mod 5 = 4

Example 2.
14
and99
are not congruent modulo7
.This is because
99  14 = 85
and85
is not a multiple of7
. Equivalently, it suffices to check that14
and99
have different remainders when divided by7
:14 mod 7 = 0
99 mod 7 = 1
To learn more about the modulo operation, and in particular its reallife applications, visit our dedicated modulo calculator.
We are ready to learn what the inverse modulo is!
What is inverse modulo?
Let a
and x
be integers. We say that x
is a modular inverse of a
when an algebraic operation performed on x
and a
yields the identity element.
Depending on whether the operation in question is addition or multiplication, we distinguish two types of modular inverses: additive and multiplicative.
Let's talk more about these two notions:
Modular additive inverse
In the case of addition, the identity element is 0
. We then say that x
is an additive inverse of a
modulo m
if a + x
and 0
are congruent modulo m
:
a + x ≡ 0 mod m
An additive inverse of a
modulo m
always exists for every a
and m
. It's given by any number of the form –a + k × m
, where k
is an integer. We usually want to find the inverse in the range {0, ... , m  1}
, i.e., in the set of remainders of division by m
.
How to find the modular additive inverse by hand? It's super easy! Here are the steps you can follow to find the additive modular inverse of a
modulo m
:
 Write down
a
.  Write down the numbers created by repeatedly adding or subtracting
m
toa
.  Pick the number that falls between
0
andm  1
.
Let's see how it works.

Example 1.
Let us find the additive inverse of
4
modulo30
.The numbers of the form
–4 + 30k
are:..., 4, 26, 56, ...
.Hence, in the set
{0, ..., 29}
the additive inverse of4
modulo30
is26
. 
Example 2.
Let us find the additive inverse of
44
modulo13
.The numbers of the form
–44 + 13k
are:..., 44, 31, 18, 5, 8, 22...
.Hence, in the set
{0, ..., 12}
the additive inverse of44
modulo13
is8
.
Modular multiplicative inverse
Recall that the identity element of multiplication is 1
. Hence, x
is a multiplicative inverse of a
modulo m
if a × x
and 1
are congruent modulo m
:
a × x ≡ 1 mod m
Unlike additive inverses, the multiplicative modular inverse does not always exist! If it does exists, however, all numbers of the form x + k × m
satisfy the required congruency. In particular, in such cases you can always find the solution (exactly one!) in the range {1, ... , m  1}
.
An Example
There is no multiplicative modular inverse of
2
modulo6
. You can verify this claim by checking that forx ∊ {1, 2, 3, 4, 5}
the operation2 × x (mod 6)
does not yield1
.
It's vital you remember that the multiplicative modular inverse of a
modulo m
exists if and only if a
and m
are relatively prime, i.e. their greatest common divisor (GCD, a.k.a. greatest common factor, GCF) equals one. We also call such numbers coprime. In particular, if m
is prime, then the multiplicative modular inverse modulo m
exists for any a ≠ 0
that is not a multiple of m
.
The whole theory of modular inverses may seem a bit abstract, and you are probably wondering, "Why would anyone care about modular multiplicative inverses?." Well, you should know that the computation of modular multiplicative inverses is essential in cryptography, and in particular in the RSA encryption method. This means that modular multiplicative inverses protect your credit card!
Obviously, the quickest method of determining multiplicative modular inverses is to use our inverse modulo calculator! 😉 However, if you need to learn how to find the modular inverse by hand, check the next section.
🙋 The multiplicative modular inverse is linked to modular exponentiation  go to Omni's power mod calculator to learn more!
How to find the modular inverse?
In this section, we explain how to find the multiplicative modular inverse. There are three main methods:
 The naive method (also called the brute force method, it's simple but slow);
 The extended Euclidean algorithm (faster, works in all cases); and
 The Fermat's little theorem (faster, prettier, but works only in some cases).
No matter which method you use, the first step is to make sure that the multiplicative modular inverse exists: recall that you have to check if a
and m
are coprime, i.e., if gcd(a,m) = 1
. To do this, you can use our GCD and LCM calculator.
Naive method
A naive method consists of trying all numbers from the set {0, ..., m  1}
. For every number x
from this set, calculate a × x mod m
, i.e., the remainder from the division of a × x
by m
.
The modular multiplicative inverse of a
modulo m
is the value of x
for which this remainder is equal to 1
.
Extended Euclidean algorithm
The second method employs Bézout's identity and the extended Euclidean algorithm.
Bézout's identity. Assume that a
and b
are integers. There exist two integers x
and y
such that: a × x + b × y = gcd(a, b)
.
Recall that the gcd(a, b)
along with the integers x
and y
, the existence of which is guaranteed by Bézout's identity.
Now, let's see how to use this theory to find the multiplicative inverse of a
modulo m
:

Recall that
a
andm
are assumed to be relatively prime, so we know thatgcd(a,m) = 1
. 
Hence, from Bézout's identity we know that:
a × x + m × y = 1
for some integers
x
andy
. We use the extended Euclidean algorithm to find them. 
Now, let's see how it's connected to the multiplicative modular inverse. Applying the
mod m
operation to both sides of the above equation, we obtain:a × x + m × y ≡ 1 (mod m)

As every multiplicity of
m
is congruent to0
modulom
, we get in particular,m × y ≡ 0 (mod m)
. As a result, we can simplify our equation to:a × x ≡ 1 (mod m)
But hey, this last equation says that the integer x
found by the extended Euclid algorithm is precisely the multiplicative inverse of a
modulo m
! By the way, this is the method our inverse modulo calculator utilizes 😀
Fermat's little theorem
The last method uses Fermat’s little theorem. We assume that m
is a prime number and a
is not a multiplicity of m
.
Fermat’s little theorem.
If m is prime and a is not divisible by m, then a^{m1}  1 is divisible by m.
We can write the claim of Fermat's little theorem as:
a^{m1}  1 ≡ 1 mod m
which, in turn, we can rewrite as
a × a^{m2}  1 ≡ 1 mod m
This equation says that the multiplicative inverse of a
modulo m
is equal to a^{m2}.
How to use this inverse modulo calculator?
The instruction of using the inverse modulo calculator is straightforward:
 Choose the type of modular inverse you're interested in finding:
 Modular multiplicative inverse; or
 Modular additive inverse.
 Enter the coefficients of the equation you want to solve.
 Our inverse modulo calculator will display the answer along with a short explanation.
Does 101 have a multiplicative inverse modulo 4620?
Yes, 101 and 4620 are coprime (their only common factor is 1), so the multiplicative inverse of 101 mod 4620 exists. We can easily verify that it equals 1601, because 101 × 1601 ≡ 161701
and 161701 = 4620 × 35 + 1
; that is, 101 × 1601 = 1 (mod 4620 )
. However, while verification is easy, finding the result in the first place requires using the extended Euclidean algorithm.
How do I find the additive inverse of 15 modulo 7?
To determine the additive inverse of 15 mod 7:
 Write down
15
, i.e., the opposite of the number whose modulo you need.  Repeatedly add
7
to15
. In this way, we obtain the sequence15, 8, 1, 6, 13, 20
...  From this sequence, we pick the number between
0
and6
. It is6
.  We have found the additive inverse of 15 mod 7!
How do I check if the modular inverse exists?
To verify if the modular inverse of a
modulo m
exists, you need to check if a
and m
are coprime. To this end:
 List all factors (divisors) of
a
.  List all factors (divisors) of
m
.  Check if the only common factor is
1
.
What numbers have inverses modulo 10?
Recall that a number must be coprime with 10 to have a multiplicative inverse modulo 10. We can easily check that:
1, 3, 7, 9
are coprime with10
, so each of them has a multiplicative inverse modulo 10, which can be computed with the help of the extended Euclid algorithm.2, 4, 5, 6, 8
are not coprime with 10, so none of them has a multiplicative inverse modulo 10.