﻿ Calculating multiplicative inverse using Extended Euclidean Algorithm
Calculating the

# Multiplicative inverse

of a number modulo n using the Extended Euclidean Algorithm

I also assume that you understand the and notation.

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 Zn, 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?
Hint:
Try to think of the answer before clicking the button below.

• 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

Question:
What is the multiplicative inverse of 3 in Z10?

Question:
What is the multiplicative inverse of 8 in Z10?
• .
How to calculate the multiplicative inverse of an integer?
We can do this using the Extended Euclidean Algorithm.
However, we don't need the s-columns (s1, s2, s3) from the algorithm to find the answer, so we can use less columns.

If you have to find the inverse of an integer b in Zn (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, as you don't need them.
• continue until r=0. When r=0, only finish the row and then stop.
When you are done:
• 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 multiplicative inverse of 11 in Z26.

So b=11 and n=26. Now we use the Extended Euclidean Algorithm with a=n=26 and b=11.
n b q rt1t2t3
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 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. This is -7.
t2 mod n = (-7) mod 26 = 19.
The multiplicative inverse of 11 modulo 26 is 19.

We can check this by verifying that a × b = 1 mod n:
11 × 19 = 209
209 mod 26 = 1.
So yes, the answer is correct.

Calculator
You can also use our calculator (click) to calculate the multiplicative inverse of an integer modulo n using the Extended Euclidean Algorithm.