Multiplicative Inverse Modulo Calculator
Table of contents
What is the multiplicative inverse in modular arithmetic?When does the multiplicative modular inverse exist?How to use this multiplicative inverse modulo calculator?Finding the multiplicative modulo inverse with Bézout's identityFAQsThe 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:
- Enter a positive integer
m: the number with which we calculate the modulo. - Enter an integer
a: the number whose multiplicative inverse modulomwe look for. - 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 .
How do I find the multiplicative modulo inverse by hand?
To find the multiplicative inverse of a modulo m by brute force:
- Take any number
xfrom the set{0, 1, ..., m − 1}and calculatea × x. - Find the remainder from the division of
a × xbym. - If this remainder is
1, you've found the solution. - If not, repeat Steps 1–3 for a different number
x. - If all numbers from
{0, 1, ..., m − 1}fail, then the multiplicative inverse ofamodulomdoes 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.