Inverse Modulo Calculator

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!

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

To learn more about the modulo operation, and in particular its real-life applications, visit our dedicated modulo calculator.

We are ready to learn what the inverse modulo is!

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:

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.

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 extended Euclidean algorithm 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.

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

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

a^m-1 - 1 ≡ 1 mod m

which, in turn, we can rewrite as

a × a^m-2 - 1 ≡ 1 mod m

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

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
   • Modular additive inverse.
2. Enter the coefficients of the equation you want to solve.
3. Our inverse modulo calculator will display the answer along with a short explanation.