Inverse type
Multiplicative
We look for x such that:
a * x = 1 mod m
a
m

# Inverse Modulo Calculator

By Anna Szczepanek, PhD

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.

## 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 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`.

 Fermats’s little theorem If `m` is prime and `a` is not divisible by `m`, then `aᵐ⁻¹ - 1` is divisible by `m`.

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

`aᵐ⁻¹ ≡ 1 mod m`

which, in turn, we can rewrite as

`a * aᵐ⁻² ≡ 1 mod m`

This equation says that the multiplicative inverse of `a` modulo `m` is equal to `aᵐ⁻²`.

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