# Inverse Modulo Calculator

Created by Anna Szczepanek, PhD
Reviewed by Dominik Czernia, PhD and Jack Bowater
Last updated: Mar 11, 2023

Welcome 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 (non-zero). 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 and 99 are congruent modulo 5:

14 ≡ 99 (mod 5)

because 99 - 14 = 85 and 85 is a multiple of 5. Equivalently, we see that 14 and 99 have the same remainder when divided by 5:

14 mod 5 = 4

99 mod 5 = 4

• Example 2.

14 and 99 are not congruent modulo 7.

This is because 99 - 14 = 85 and 85 is not a multiple of 7. Equivalently, it suffices to check that 14 and 99 have different remainders when divided by 7:

14 mod 7 = 0

99 mod 7 = 1

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:

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:

1. Write down -a.
2. Write down the numbers created by repeatedly adding or subtracting m to a.
3. Pick the number that falls between 0 and m - 1.

Let's see how it works.

• Example 1.

Let us find the additive inverse of 4 modulo 30.

The numbers of the form –4 + 30k are: ..., -4, 26, 56, ....

Hence, in the set {0, ..., 29} the additive inverse of 4 modulo 30 is 26.

• Example 2.

Let us find the additive inverse of 44 modulo 13.

The numbers of the form –44 + 13k are: ..., -44, -31, -18, -5, 8, 22....

Hence, in the set {0, ..., 12} the additive inverse of 44 modulo 13 is 8.

#### 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 modulo 6. You can verify this claim by checking that for x ∊ {1, 2, 3, 4, 5} the operation 2 * x (mod 6) does not yield 1.

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 allows us to effectively determine 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:

1. Recall that a and m are assumed to be relatively prime, so we know that gcd(a,m) = 1.

2. Hence, from Bézout's identity we know that:

a * x + m * y = 1

for some integers x and y. We use the extended Euclidean algorithm to find them.

3. 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)

4. As every multiplicity of m is congruent to 0 modulo m, 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.

Fermats’s little theorem.
If m is prime and a is not divisible by m, then am-1 - 1 is divisible by m.

We can write the claim of Fermat's little theorem as

am-1 - 1 ≡ 1 mod m

which, in turn, we can rewrite as

a × am-2 - 1 ≡ 1 mod m

This equation says that the multiplicative inverse of a modulo m is equal to am-2.

## How to use this inverse modulo calculator?

The instruction of using the inverse modulo calculator is straightforward:

1. Choose the type of modular inverse you're interested in finding:
• Modular multiplicative inverse; or
1. Enter the coefficients of the equation you want to solve.
2. Our inverse modulo calculator will display the answer along with a short explanation.

## FAQ

### 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:

1. Write down -15, i.e., the opposite of the number whose modulo you need.
2. Repeatedly add 7 to -15. In this way, we obtain the sequence -15, -8, -1, 6, 13, 20...
3. From this sequence, we pick the number between 0 and 6. It is 6.
4. 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:

1. List all factors (divisors) of a.
2. List all factors (divisors) of m.
3. 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 with 10, 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.
Anna Szczepanek, PhD
Inverse type
Multiplicative
We look for x such that:
a * x = 1 mod m
a
m
People also viewed…

### (Reduced) row echelon form

The (reduced) row echelon form calculator uses the Gauss (or Gauss-Jordan) elimination to find the solution of a system of up to three equations.

### Completing the square practice

Here you can find practice questions for the method of solving quadratic equations by completing the square.

### Meat footprint

Check out the impact meat has on the environment and your health.

### Plastic footprint

Find out how much plastic you use throughout the year with this plastic footprint calculator. Rethink your habits, reduce your plastic waste, and make your life a little greener.