E.E.A. .com
It doesn't have to be difficult if someone just explains it right.

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:

Here are some things vaguely described, such that you get an idea of what these notations mean.

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:

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.

(s × n) + (b × t) = 1
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:

Once you are done with creating the table:


Find the modular multiplicative inverse of 11 in ℤ26.

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.

nbqr t1t2t3

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.


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!