Modular Multiplicative Inverse
Calculating the modular multiplicative inverse of a number modulo n, using the Extended Euclidean Algorithm.
Before you read this page
Make sure to read these pages (or watch the videos) first, otherwise this page is confusing:
- Euclidean Algorithm (including the table notation)
- Extended Euclidean Algorithm
ℤ is the set of all integers
So ℤ = {..., -3, -2, -1, 0, 1, 2, 3, ...}
ℤn is that same set, but then with mod n applied to all numbers.
If you remove all the duplicates in a set after applying mod n to the numbers, you'll see that it is a finite set, with
ℤn = {0, 1, 2, ..., n−1}.
If we choose n=6 for example, we have ℤ6 = {0, 1, 2, 3, 4, 5}.
And with n=15, we get ℤ15 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}.
Operations are things like + and ×. You can use them on elements in these sets.
If you have a set and such a operation, then you can call that a group if they satisfy some requirements together. One of those requirements is that if you use the operation on two elements in the set, the result of that operation is another element that's also part of that set. To be more precise, the requirements are: associativity, inverse, identity, closure, commutativity and stuff like that. Look it up if you want to know more about it.
Table of contents:
What is an inverse?
The inverse of a number depends on the operation that is used.
Here are two examples:
- Additive inverse
When we use addition (+) as operation (e.g. 1+1), then the inverse of a number (relative to addition) is called the additive inverse.
In ℤn, two numbers a and b are additive inverses of each other if:
a + b ≡ 0 (mod n).
→ Important to know: each integer has an additive inverse.Question
What is the additive inverse of 2 in Z10?
a=2, n=10.
We need to find b, such that a + b ≡ 0 (mod n). In other words:
2 + what ≡ 0 (mod 10)?The answer is in the spoiler below. But try to think of the answer before looking.
It's 8, because 2 + 8 = 10, and 10 in ℤ10 is 0.
2 + 8 (mod 10) ≡ 10 mod 10 ≡ 0 (mod 10) - Multiplicative inverse
When we use multiplication (×) as operation (e.g. 2×3), then the inverse of a number (relative to multiplication) is called the multiplicative inverse.
In Zn, two numbers a and b are multiplicative inverses of each other if:
a × b ≡ 1 (mod n).
→ Important to know: not each integer has a multiplicative inverse! Only if gcd(that integer, n) == 1Question
What is the multiplicative inverse of 3 in Z10?
Again, please think of the answer yourself before clicking this thing below.n=10. Let's say b=3. Then we need to find a, such that:
a × b ≡ 1 (mod n).
So what × 3 ≡ 1 (mod 10)?
It's 7, because 7 × 3 = 21. And 21 is 1 in Z10.
7 × 3 (mod 10) ≡ 21 (mod 10) ≡ 1 (mod 10)Question
What is the multiplicative inverse of 8 in Z10? This is a nasty one.
Hint: look at the gcd.gcd(8, 10) = 2. We already said that an integer only has a multiplicative inverse if gcd(that integer, n) == 1, so 8 has no multiplicative inverse in Z10..
How to calculate the modular multiplicative inverse of an integer?
We can do this using the Extended Euclidean Algorithm.
But, a cool thing is that we don't need the s-columns (s1, s2, s3) from the algorithm to find the answer,
so we can use less columns.
Now apply mod n to both sides:
(s × n) + (b × t) mod n ≡ 1 mod n
This is the same as:
(s × n) mod n + (b × t) mod n ≡ 1 mod n
s × n is divisible by n (since you multiply s by n), so s × n mod n ≡ 0 mod n:
0 mod n + (b × t) mod n ≡ 1 mod n
This is the same as
(b × t) mod n ≡ 1 mod n
So t is the multiplicative inverse of b in ℤn. This value will be in the t-columns, hence we do not need the s-columns
General way of doing it
If you have to find the inverse of an integer b in ℤn (or of an integer b modulo n), then:
- use the Extended Euclidean Algorithm with a=n and b
- do not write down the s-columns, since you don't need them.
- continue until r=0. When r=0, only finish that row and then stop.
- column b on the last row will contain the answer of gcd(n, b).
This should be 1, otherwise b has no multiplicative inverse! - If gcd(n, b) indeed equals 1, then we need the value in column t2 in the last row.
Let's call that value t2. - The answer is t2 mod n
Example
Find the modular multiplicative inverse of 11 in ℤ26.
Answer:
So b=11 and n=26.
Now we use the Extended Euclidean Algorithm with a=n=26.
This means that instead of using a as the first column (like we normally do in the Extended Euclidean Algorithm), we use n.
The second column is still b, starting with b=11.
| n | b | q | r | t1 | t2 | t3 |
|---|---|---|---|---|---|---|
| 26 | 11 | 2 | 4 | 0 | 1 | -2 |
| 11 | 4 | 2 | 3 | 1 | -2 | 5 |
| 4 | 3 | 1 | 1 | -2 | 5 | -7 |
| 3 | 1 | 3 | 0 | 5 | -7 | 26 |
Column b on the last row has the value 1, so gcd(n, b) = 1.
This is exactly what we want, because now
we know that 11 has a multiplicative inverse modulo 26.
So we need the value of column t2 on the last row. Let's call this value t. As you can see in the table, this is -7, so t=-7.
Now we apply mod n to that number. So we do this:
t mod n ≡ (-7) mod 26 ≡ 19.
This is our answer: the multiplicative inverse of 11 modulo 26 is 19.
Verification
Let's call the answer we just found i (i as in inverse).
We can check that we found the right answer by verifying that i × b ≡ 1 (mod n):
So b=11, n=26 and i=19.
Then i × b (mod 26) ≡
19 × 11 (mod 26) ≡
209 (mod 26) ≡ 1 mod (26).
209 ≡ 1 (mod 26)
So yes, i × b ≡ 1 (mod n), meaning that the answer is correct.
More examples? Check the calculator!
And of course our cool modular multiplicative inverse calculator can do this entire process for you!Enter the numbers you want and the calculator will calculate the multiplicative inverse of b modulo n using the Extended Euclidean Algorithm.
It will also show you the verification!