Multiplicative Inverse Modulo Calculator

The multiplicative inverse modulo calculator is of immeasurable value whenever you need to quickly find the multiplicative inverse modulo for some m, be it for a math assignment, a programming project, or any other scientific endeavor you deal with.

In the brief article below, we'll explain how to find the multiplicative inverse modulo — both by Bézout's identity and by brute force (depending on how much you care about mathematical subtlety). And to spare you useless work, we'll also tell you how to check if the multiplicative modular inverse exists in the first place.

Let a and x be integers. We say that x is the modular multiplicative inverse of a (modulo m) if

a × x ≡ 1 (mod m).

That is, when a × x and 1 are congruent modulo m, i.e., when (a × x) mod m = 1.

In even simpler words, the remainder from the division of a × x by m must equal 1.

The modular multiplicative inverse of a modulo m exists if and only if a and m are coprime (a.k.a. relatively prime), i.e., if their greatest common factor equals one: gcd(a,m) = 1.

If m is prime, then the multiplicative modular inverse modulo m exists for every non-zero integer a that is not a multiple of m.

As you can see, it's easy to verify if the multiplicative modular inverse exists, but computing it is quite a different story. The fastest method is to use our multiplicative inverse modulo calculator!

Using this multiplicative inverse modulo calculator is really simple:

1. Enter a positive integer m: the number with which we calculate the modulo.
2. Enter an integer a: the number whose multiplicative inverse modulo m we look for.
3. Our calculator returns the answer immediately. A short explanation is provided as well.

Are you curious how our tool can solve this modulo problem so quickly? In the next section, we explain the method implemented in our calculator.

Let a and m be integers. Bézout's identity says that there exist two integers x and y such that:

a×x + m×y = gcd(a, m).

That is, we can represent gcd(a, m) as a linear combination of a and m with coefficients x and y.

It turns out we can use this representation to find the multiplicative inverse of a modulo m. Recall that a and m must be coprime, so gcd(a,m) = 1 — Bézout's identity says that there exist integers x and y such that:

a×x + m×y = 1

Next, we apply the mod m operation to both sides:

(a×x + m×y) mod m = 1 mod m
⇒ a×x + m×y ≡ 1 (mod m)

The second form is just short-hand for the first form — they mean the same. The left-hand side simplifies to a×x because m×y is divisible by m. That is, we get:

a×x ≡ 1 (mod m)

This means that we have the solution right in front of our eyes: x is the multiplicative inverse of a modulo m!

To find the multiplicative inverse of a modulo m by brute force:

1. Take any number x from the set {0, 1, ..., m − 1} and calculate a × x.
2. Find the remainder from the division of a × x by m.
3. If this remainder is 1, you've found the solution.
4. If not, repeat Steps 1–3 for a different number x.
5. If all numbers from {0, 1, ..., m − 1} fail, then the multiplicative inverse of a modulo m does not exists.

No — if x is a multiplicative inverse of a modulo m, then every number of the form x + (k×m) (where k is an integer) is a multiplicative inverse of a modulo m as well. However, the solution is unique in the set {1, ..., m − 1}.

No, 142 does not have a multiplicative inverse modulo 76. The reason is that these numbers are not relatively prime, i.e., their greatest common factor exceeds 1. Indeed, we immediately see that both 142 and 76 are both divisible by 2.

Every integer that is not a multiple of 11 has a multiplicative inverse modulo 11. This is because 11 is a prime number, and so it is not coprime only with its multiplicities. Calculating the multiplicative inverses may be tiresome, so don't hesitate to use an online multiplicative inverse modulo calculator.