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
$\mathbb{Z}$ is the set of all integers. So:
$$\mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ...\}$$
$\mathbb{Z}_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
$$\mathbb{Z}_n = \{0, 1, 2, ..., n−1\}$$
If we choose $n=6$ for example, we have
$$\mathbb{Z}_6 = \{0, 1, 2, 3, 4, 5\}$$
And with $n=15$, we get $$\mathbb{Z}_{15} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}$$
Operations are things like $+$ and $\times$. 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 $\mathbb{Z}_n$, two numbers $a$ and $b$ are additive inverses of each other if:
$$a + b \equiv 0 \pmod{n}$$ → Important to know: each integer has an additive inverse.Question
What is the additive inverse of $2$ in $\mathbb{Z}_{10}$?
$a=2$, $n=10$.
We need to find $b$, such that $a + b \equiv 0 \pmod{n}$. In other words: $2 + \text{ what } \equiv 0 \pmod{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 $\mathbb{Z}_{10}$ is $0$.
$2 + 8 \pmod{10} \equiv 10 \pmod{10} \equiv 0 \pmod{10}$ - Multiplicative inverse
When we use multiplication $×$ as operation (e.g. $2 \times 3$), then the inverse of a number (relative to multiplication) is called the multiplicative inverse.
In $\mathbb{Z}_n$, two numbers $a$ and $b$ are multiplicative inverses of each other if:
$$a × b \equiv 1 \pmod{n}$$ → Important to know: not each integer has a multiplicative inverse! Only if $gcd(\text{that integer}, n) == 1$Question
What is the multiplicative inverse of $3$ in $\mathbb{Z}_{10}$?
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 \times b \equiv 1 \pmod{n}$.
So $\text{what} × 3 \equiv 1 \pmod{10}$?
It's $7$, because $7 \times 3 = 21$. And $21$ is $1$ in $\mathbb{Z}_{10}$.
$7 \times 3 \pmod{10} \equiv 21 \pmod{10} \equiv 1 \pmod{10}$Question
What is the multiplicative inverse of $8$ in $\mathbb{Z}_{10}$? 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(\text{that integer}, n) == 1$, so $8$ has no multiplicative inverse in $\mathbb{Z}_{10}$..
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.
So let's apply $\pmod{n}$ to both sides, because why not: $$(s \times n) + (b \times t) \pmod{n} \equiv 1 \pmod{n}$$ This is the same as: $$(s \times n) \pmod{n} + (b \times t) \pmod{n} \equiv 1 \pmod{n}$$ $s \times n$ is divisible by $n$ (since you multiply $s$ by $n$), so $s \times n \pmod{n} \equiv 0 \pmod{n}$: $$0 \pmod{n} + (b \times t) \pmod{n} \equiv 1 \pmod{n}$$ This is the same as $$(b \times t) \pmod{n} \equiv 1 \pmod{n}$$ So $t$ is the multiplicative inverse of $b$ in $\mathbb{Z}_{n}$. This value will be in the t-columns, hence we do not need the s-columns
Our goal
To calculate a multiplicative inverse of a number $t \pmod{n}$, we want to find a $t$ such that: $$t \times b \equiv 1 \pmod{n}$$
(Remember that in the Extended Euclidean algorithm we wanted to find an $s$ and $t$ such that $s \times a + t \times b = gcd(a, b)$. When using the Extended Euclidean Algorithm to find a multiplicative inverse, we're basically on a lite version of this quest. So we can now use a simpler version of this formula. See the spoiler above to understand more about this).
General way of doing itIf you have to find the inverse of an integer $b$ in $\mathbb{Z}_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 \pmod{n}$
Example
Find the modular multiplicative inverse of 11 in $\mathbb{Z}_{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$.
(If this value of $b$ on the last row would be any other number than $1$, we would just stop here and say "11 has no multiplicative inverse modulo 26". But that's not the case, so let's continue)
So we need the value of column $t2$ on the last row. Let's also refer to this value as $t2$. As you can see in the table, the value of the column $t2$ in the last row is $-7$, so we just say $t2=-7$.
Our final answer $t$ is that number with $\pmod{n}$ applied to it. Let's do that::
$$t \equiv t2 \pmod{n} \equiv (-7) \pmod{26} \equiv 19$$
This is our answer: the multiplicative inverse of $11$ modulo $26$ is $19$.
Verification
We can check that we found the right answer by verifying that $t \times b \equiv 1 \pmod{n}$:
So $b=11$, $n=26$ and $t=19$.
Then
\[
\begin{aligned}
t \times b \pmod{n} &\equiv \\
19 \times 11 \pmod{26} &\equiv \\
209 \pmod{26} &\equiv 1 \pmod{26} \\
&\equiv 1 \pmod{n} \\
\end{aligned}
\]
So yes, $t \times b \equiv 1 \pmod{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!