Modular Inverse of a Number

The modular inverse of a number a modulo n is a number b such that their product, taken modulo n, equals 1: $$ ab \equiv 1 \ (\text{mod} \ n) $$

If b is the modular inverse of a, we write it as $ b = a^{-1} $.

$$ a \cdot b = a \cdot a^{-1} = a \cdot \frac{1}{a} = 1 $$

In other words, multiplying a by its modular inverse gives 1.

A Practical Example
How to Compute the Modular Inverse of a Number
Example

A Practical Example

Let's consider the integer $ a = 5 $ modulo 6:

$$ a = 5 \ \in Z_6 $$

We need to find a number $ b $ such that:

$$ a \cdot b \equiv 1 \ (\text{mod} \ 6) $$

Note: This is equivalent to finding a number $ b $ such that the remainder of the product $ ab $ divided by $ n $ is 1: $$ (ab) \ \% \ n = 1 $$

Since we are given $ a = 5 $, we solve:

$$ 5 \cdot b \equiv 1 \ (\text{mod} \ 6) $$

One simple way to find $ b $ is by checking a multiplication table, if available.

a ·₆ b	1	2	3	4	5
0	0	0	0	0	0
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	5	4	3	2	1

Here, we see that 5 is its own inverse because:

$$ (5 \cdot 5)/6 = \frac{25}{6} = 4 \ \text{remainder} \ 1 $$

So the remainder when dividing by 6 is 1:

$$ (a \cdot b) \% n = (5 \cdot 5) \% 6 = 25 \% 6 = 1 $$

Note: Not every nonzero number has a modular inverse. For example, in $ Z_6 $, the numbers 2, 3, and 4 do not have modular inverses. A modular inverse exists for every nonzero number only when $ n $ is prime.

Example 2

Now, let's examine the multiplication table for numbers modulo 5:

a ·₅ b	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Since $ n = 5 $ is a prime number, every nonzero number modulo 5 has a modular inverse:

$$ 1 \cdot 1 \equiv 1 \ (\text{mod} \ 5) $$

$$ 2 \cdot 3 \equiv 1 \ (\text{mod} \ 5) $$

$$ 3 \cdot 2 \equiv 1 \ (\text{mod} \ 5) $$

$$ 4 \cdot 4 \equiv 1 \ (\text{mod} \ 5) $$

How to Compute the Modular Inverse of a Number

To find the modular inverse of a number modulo $ n $, we use the Extended Euclidean Algorithm.

This algorithm is based on the fact that if $ a $ and $ n $ are relatively prime, there exists an integer $ x $ such that:

a · x ≡ 1 (mod n)

If $ a $ and $ n $ are not relatively prime, a modular inverse does not exist.

The problem can be rewritten using Bézout’s identity, where $ a $ and $ n $ are known values:

$$ a \cdot x + n \cdot y = 1 $$

Here, the coefficient $ x $ is the modular inverse of $ a $, while $ y $ is an auxiliary coefficient that can be ignored.

How does it work? The Extended Euclidean Algorithm finds solutions to Bézout’s identity. Since we already know that $ \gcd(a, n) = 1 $ (because $ a $ and $ n $ are coprime), we don’t need to explicitly compute the greatest common divisor. Our main goal is to determine the coefficient $ x $, which is the modular inverse.

Note: The Extended Euclidean Algorithm extends the standard Euclidean algorithm. While the standard algorithm only computes the greatest common divisor (gcd), the extended version also finds the coefficients in Bézout’s identity:

$$ ax + by = \gcd(a, b) $$

When $ a $ and $ b $ are relatively prime, Bézout’s identity simplifies to:

$$ ax + by = 1 $$

Since the gcd of two coprime numbers is always 1, there's no need to compute $ \gcd(a, b) $. If needed, we can determine which numbers are coprime to $ n $ using Euler’s totient function.

Example

Let's find the modular inverse of 23 modulo 40.

Since 23 is prime and does not divide 40, we know that 23 and 40 are coprime:

$$ \gcd(23, 40) = 1 $$

Therefore, we can apply the Extended Euclidean Algorithm.

Note: If the numbers were not coprime, the modular inverse wouldn’t exist, and this method wouldn’t apply.

We need to solve Bézout’s equation for $ a = 23 $ and $ n = 40 $:

$$ 23 \cdot u + 40 \cdot v = 1 $$

Using the Euclidean algorithm, we repeatedly divide and take remainders until we reach 1.

At each step, we express the remainder in the form r = 23u + 40v.

	Remainder
$$ 40 \div 23 = 1 \times 23 + 17 $$	$$ 17 = 40 - 23 $$ $$ 17 = 40 \cdot 1 + 23 \cdot (-1) $$
$$ 23 \div 17 = 1 \times 17 + 6 $$	$$ 6 = 23 - 17 $$ $$ 6 = 23 - (40 - 23) $$ $$ 6 = 23 \cdot 2 - 40 $$ $$ 6 = 23 \cdot 2 + 40 \cdot (-1) $$
$$ 17 \div 6 = 2 \times 6 + 5 $$	$$ 5 = 17 - 2 \cdot 6 $$ $$ 5 = (40 - 23) - (23 \cdot 2 - 40) \cdot 2 $$ $$ 5 = 40 - 23 - 23 \cdot 4 + 40 \cdot 2 $$ $$ 5 = -23 \cdot 5 + 40 \cdot 3 $$ $$ 5 = 23 \cdot (-5) + 40 \cdot 3 $$
$$ 6 \div 5 = 1 \times 5 + 1 $$	$$ 1 = 6 - 5 $$ $$ 1 = [23 \cdot 2 + 40 \cdot (-1)] - [23 \cdot (-5) + 40 \cdot 3] $$ $$ 1 = 23 \cdot 2 + 40 \cdot (-1) + 23 \cdot 5 + 40 \cdot (-3) $$ $$ 1 = 23 \cdot (2 + 5) + 40 \cdot (-1 - 3) $$ $$ 1 = 23 \cdot 7 + 40 \cdot (-4) $$

Since the remainder is now 1, we stop.

From Bézout’s equation:

$$ 1 = 23 \cdot 7 + 40 \cdot (-4) $$

The modular inverse of 23 modulo 40 is the coefficient of 23 in this equation:

$$ 1 = 23 \cdot \color{red}7 + 40 \cdot (-4) $$

Thus, the modular inverse of 23 (mod 40) is 7.

Verification: We check by computing $ 23 \cdot 7 $ modulo 40:

$$ 23 \cdot 7 \ (\text{mod } 40) $$

$$ 161 \ (\text{mod } 40) $$

$$ 161 = 40 \times 4 + 1 $$

The remainder is 1, confirming that our calculation is correct.

And that’s how you compute modular inverses using the Extended Euclidean Algorithm!