MODULAR INVERSES

by Matthew Holmes

What are multiplicative inverses?

Given some initial number, a multiplicative inverse is whatever number that you need to multiply by your initial number so the result is $1$ . This much is always true; whether we’re using real numbers, fractions, or modular arithmetic. Let’s say we’re using ”regular” whole numbers and are allowed fractions. Then, if our initial number is 2, then its multiplicative inverse is $\frac{1}{2}$ . How do we know this is the inverse? It’s not just because we ”took 1 over” the original number. It’s because when you multiply 2 and $\frac{1}{2}$ the result is 1. That may seem trivial, but this intuition will hold true when we start working with modular arithmetic. However, with modular arithmetic, multiplicative inverses aren’t a fraction like we’ve just seen; they’re just another number.

To illustrate the difference, let’s find the inverse of 2 (mod 5). Since we don’t have access to fractions, we’ll denote this number $2^{-1} \hspace{2mm} (mod \hspace{2mm} 5)$ . As we’ll calculate later, $2^{-1} \equiv 3 \hspace{2mm} (mod \hspace{2mm} 5)$ , and that’s because $2 * 3 \equiv 1 \hspace{2mm} (mod \hspace{2mm} 5)$ . So instead of being some easy to recognize fraction like $\frac{1}{2}$ , it’s just some other number: 3. Note: the inverse changes depending on the modulus! For example, $2^{-1} \equiv 4 \hspace{2mm} (mod \hspace{2mm} 7)$ . What it means to be an inverse, however, is the same: each number has its own inverse¹, and it’s the number you need to multiply by so the result is 1.

How are they used?

Division; division by any number is the same as multiplying by its inverse (if the inverse exists). Again, this much is always true whether we’re dealing with ”regular” numbers or with modular arithmetic. So to continue with our example from above, if we wanted to divide by 2, the result is equivalent to multiplying by $\frac{1}{2}$ . The same will be true with modular arithmetic, but we aren’t allowed fractions. For example, if we want to divide by 2 (mod 5), that’s equivalent to multiplying by 3 (mod 5).

In the first week, we’ll see how inverses are used in RSA key generation, and later in the course, we’ll need multiplicative inverses when we calculate slopes required for Elliptic Curves!

How to calculate them?

From here on out, we’ll assume we’re working with modular arithmetic. That said, there’s a few ways to calculate inverses: brute force, Euclid’s Algorithm, an application of the Euler-Fermat theorem, python, and others. We’ll describe the first three.

Brute Force

This really only works if the numbers are small, but will help to illustrate the definitions we’ve discussed. So let’s assume we’re looking for the inverse of 2 (mod 5). Remember, we’re looking for the number to multiply by 2 so the result is 1 (mod 5). So let’s just try all of them:

2 * 1 ≡ 2 (mod 5) (no)
2 * 2 ≡ 4 (mod 5) (also no)
2 * 3 = 6 ≡ 1 (mod 5) (yes! that’s it)²

So we can say that $2^{-1} \equiv 3 \hspace{2mm} (mod \hspace{2mm} 5)$ via brute force.

Euclid’s Algorithm

Euclid’s algorithm is mainly used to tell if two numbers share any common factors, but its Extended version can also help us find multiplicative inverses for modular arithmetic. Let’s use it to find $2^{-1} \equiv 3 \hspace{2mm} (mod \hspace{2mm} 5 )$ . To do this, we’ll run gcd(2, 5) and make sure the result is 1³:

$5 = 2 * 2 + 1$
$1 = 5 - 2 * 2$

That was a short application of Euclid’s Algorithm, but we can see from the equation on the left that the gcd is indeed 1, and the equation on the right has just solved for 1. Now, we just consider the equation on the right (mod 5):

1 ≡ 5 − 2 * 2 ≡ −2 * 2 ≡ 3 * 2 (mod 5)

If we look at the book-ends of this string of congruences, we see that 1 ≡ 2 * 3 (mod 5), so 2 − 1 ≡ 3 (mod 5) via Euclid’s Algorithm.

Euler-Fermat

We can use the Euler-Fermat theorem (and a special case of it) to find modular inverses as well! As a reminder, the Euler-Fermat theorem is the following:

$m^{\phi(n)} \equiv 1 \hspace{2mm} (mod \hspace{2mm} n)$ (as long as gcd(m, n) = 1)

We can re-arrange this to get the following:

$m^{\phi(n)} \equiv m \hspace{2mm} * \hspace{2mm} m^{\phi(n) - 1} \equiv 1 \hspace{2mm} (mod \hspace{2mm} n)$

and multiplying by $m^{-1}$ on both sides gives:

$m^{-1} \equiv m^{\phi(n) - 1} \hspace{2mm} (mod \hspace{2mm} n)$

The special case mentioned earlier is if n is a prime number. This turns into the following: $m^{-1} \equiv m^{p-2} \hspace{2mm} (mod \hspace{2mm} p)$ ⁴. So if we wanted to find 2^-1 (mod 5), we just calculate:

$2^{-1} = 2^{5-2} = 2^3 = 8 \equiv 3 \hspace{2mm} (mod \hspace{2mm} 5)$

So 2^-1 ≡ 3 (mod 5) via the Euler-Fermat theorem.

_______________________________________________________________________

When discussing inverses, we’ll almost always be referring to multiplicative inverses, so will continue to refer to them as simply “inverses” ↩︎
Since inverses are unique (true, but we won’t prove it), we can stop looking as soon as we find it. ↩︎
If the result isn’t 1, the inverse does not exist! ↩︎
Because $\phi(p) \equiv p - 1$ ↩︎

CyberBear