Omni Calculator logo

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.

🙋 We assume you're already familiar with the modulo operation in math. If this is not the case (or you feel you need a refresher), check out Omni's modulo calculator.

What is the multiplicative inverse in modular arithmetic?

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.

❗ It may happen that the multiplicative inverse modulo does not exist! For instance, the multiplicative modular inverse of 3 modulo 6 does not exist: you may check yourself that for every number x ∊ {1, 2, 3, 4, 5}, the result of (3 × x) mod 6 is different from 1.

When does the multiplicative modular inverse exist?

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.

🙋 To quickly determine the greatest common divisor of two integers, use Omni's GCF calculator.

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!

How to use this 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.

Finding the multiplicative modulo inverse with Bézout's identity

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!

🔎 Finding x and y for Bézout's identity is not trivial. The best method is to use the extended Euclidean algorithm.

FAQ

How do I find the multiplicative modulo inverse by hand?

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.

Is the multiplicative inverse modulo m unique?

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}.

Does 142 have a multiplicative inverse modulo 76?

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.

What numbers have multiplicative inverses modulo 11?

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.

Anna Szczepanek, PhD
Related calculators
We look for x such that:
a × x ≡ 1 (mod m)
i.e. an x that satisfies (a × x) mod m = 1
a
m
Check out 75 similar arithmetic calculators ➗
Absolute changeAbsolute valueAdding and subtracting fractions… 72 more
People also viewed…

Adding and subtracting polynomials

The adding and subtracting polynomials calculator finds the sum or difference of two polynomials up to degree 6.

Cholesky decomposition

The Cholesky decomposition calculator lets you quickly and easily obtain the lower triangular matrix of the Cholesky factorization. Pick between a 2×2, 3×3, or a 4×4 matrix.

Helium balloons

Wondering how many helium balloons it would take to lift you up in the air? Try this helium balloons calculator! 🎈

Social Media Time Alternatives

Check what you could have accomplished if you get out of your social media bubble.
Copyright by Omni Calculator sp. z o.o.
Privacy, Cookies & Terms of Service