# Modular Multiplicative Inverse

Calculating the modular multiplicative inverse of a number modulo n, using the Extended Euclidean Algorithm.

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.

#### What is an inverse?

The inverse of a number depends on the operation that is used.
Here are two examples:

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.

• 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) == 1

• .

#### 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:

• 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.
Once you are done with creating the table:
• 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.

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
26112401-2
114231-25
4311-25-7
31305-726

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!