4 - Multiplicative Inverse

We have just gone over Multiplicative inverse, we now check how Bezouts identity and Fermats Little Theorem can help us. This marks the end of our quest for the multiplicative inverse!

Fermat’s Little Theorem

Motivation

When finding the multiplicative inverse of a mod q , we need to first check if a is coprime to q.

For a prime number p, all positive numbers less than p is co-prime to p.

It is therefore advantageous to quickly find out when a modulus is prime or not.

Fermat’s Little Theorem gives us a way to check if a number is a prime number with a simple equation.

Theorem

Let p be a prime, $\forall a \in \mathbb{Z}$, $a^p \equiv a$ mod $p$.

Notice, that this check says nothing about composite numbers. Hence, $a^p \equiv a$ mod $p$ can be true for composite numbers too.

Counter example for composite

An counter example is : $11^{15} = 11$ mod 15 but 15 is composite. If we try for a few more random numbers, we see that Fermat’s Theorem does not hold $\forall a$, as soon as we find a counter-example, we know that it is not a prime.

Bezout’s Identity

Motivation

When finding the multiplicative inverse, we first check whether the gcd is equal to one. It would be advantageous to be able to write the gcd of a and b in terms of their linear combinations.

Theorem

Let $a,b \in \mathbb{Z}$ $\exists$ $x,y \in \mathbb{Z}$ such that $ax+by=gcd(a,b)$

Written: given two integers a and b, we can find a linear combination of a and b which is equal to the greatest common divisor of a and b.

Example

If I want to find the multiplicative inverse of 3 mod 7.

I first note that gcd(7, 3) = 1. By Bezouts theorem, I can write 3 and 7 as a linear combinationation of the gcd.

$3x +7y = gcd(3,7)$

$3x +7y = 1$

Applying the modulus to both sides:

($3x$ mod 7) + ($7y$ mod 7) = (1 mod 7)

This simplifies to:

$3x$ mod 7 = 1 mod 7

But how do we find x and y? x is the multiplicative inverse. How do we find x? We can use the Extended Euclidean Algorithm!

Putting it all together

In our mathematical toolbox, we have the following tools to find the multiplicative inverse:

• Euclidean algorithm; that allows us to find the greatest common divisor
• Bezout’s Identity: Which allows us the represent the greatest common divisor of a and b as ax+by
• Extended Euclidean Algorithm: which allows us to find the values of x and y in Bezout’s identity.

Example

Goal: Find the multiplicative inverse of 10 mod 23.

First we apply the Euclidean algorithm, which tells us that gcd(10,23) = 1. So the multiplicative inverse exists.

Now we apply Bezout’s algorithm to express the gcd as $10x+23y = 1$

Finally, we apply the Extended Euclidean algorithm to find the values of x and y. $x=7$ and $y=-3$

We now know that $10 \times 7 + 23 \times (-3) = 1$

Applying (mod 23) to both sides: $10 \times 7$ mod 23 = 1 mod 23

The multiplicative inverse of 10 mod 23 is therefore 7 mod 23.