Calculating the

Multiplicative inverse

of a number modulo n using the Extended Euclidean Algorithm

Before you read this page
This page assumes that you have read and understood the following pages: 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:
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: When you are done:
Example
Find the multiplicative inverse of 11 in Z26.

Answer:
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.