0:00

We conclude the lesson with another important application of the Euclid

algorithm, namely modular division or inverse as modular n.

So for this, first recall the following multiplication application table,

modulo 7.

So it gives us, for any two remainders modulo 7,

the remainder of their product modulo 7.

For example, if you remind a number with remainder modulo 7 is 5,

with a number whose remainder modulo 7 is 3,

then what you get is a number whose remainder modulo 7 is equal to 1, okay?

So with closer look at this table, reveals the following property.

In every row, except for the 0s row,

we have all 7 different integers.

For example, if we take a look at this row, it has all 7 different integers,

as well in this row, as well as all other rows except for the 0s one.

And this actually tells us the following important property.

So for any nonzero a and for any b, we can always find a number

x such that a times x is equal to b modulo 7.

So in a sense, x here is b divided by a modulo 7.

So let me illustrate this property on some core example.

So if a is equal to 3 for example, and b is equal to 5.

Then what we're looking for

is a number of x such that 3 times x is equal to 5 modulo 7.

So in a sense what we are looking for is a column such that when

intersected with the third row, we have a number 5.

And this is the fourth column, so we have the number 5 here.

So it tells us that if x is equal to 4,

then we have the right congruence here.

And indeed 3 times 4 is 12, it is congruent to 5 modulo 7.

And since all the integers are different in all of the rows except for

the 0 scores, such division is always possible.

Now let's consider another case,

let's consider multiplication table modulo 6.

So as you see this property does not hold anymore for all the rows here.

This in particular means that sometimes division is possible and

sometimes it is not.

So for example, if you would like to find a number such that when it is

multiplied by 5, it gives you a remainder 2 modulo 6.

Then what you are basically looking for is,

2:48

The number is the column such that, in this row, we have 4.

So as you see if you multiply 2 by 4,

this gives you 10, and this is indeed 4 modulo 6.

On the other hand, if you'd like to find the number x such that when multiplied

by 3 it gives you number 6, and you just cannot find such a number.

So you can not find one in this row.

And it is actually why just because any number

multiplied by 3 is always divisible by 3, right?

So if you would like 3x to be congruent to 1 modulo x,

then you essentially would like 6 to divide 3x- 1.

So if 6 divides 3x- 1, then necessarily 3 should divide 3x- 1.

But 3x- 1 cannot be divisible by 3, just because 3x is divisible by 3,

and then we multiply a number 1 which is not divisible by 3.

So as we see in this case, we cannot divide 1 by 3 modulo 6.

More formally, we cannot the number x such that 3x is congruent to 1 modulo 6.

So at this point it is natural and it is important to ask,

in what cases we can divide by a, okay?

So let's first define the multiplicative Inverse modular n.

So the multiplicative inverse or a modular n is a number a bar

such that a times a bar is congruent to 1 modulo n.

So now it is important to understand that if we have a multiplicative

inverse modulo n, then we can divide any number of b by a in this case.

Namely, we can always find a number x such that a times x is congruent to b modulo n.

And such, such an x is just equal to b times a bar, where a bar is an inverse.

So let me illustrate this.

So for any number b if we multiply such an x,

which we defined as b divided by a,

then this is b times a bar multiplied by a.

But this is just 1 just by the definition of the multiplicative inverse.

So if you multiple this x by a, you get b as desired, right?

So if a has a multiplicative inverse, then for any number b,

we can find the number x such that ax is congruent to b modulo n, okay?

So now it is important to understand when a has a multiplicative inverse.

But before this, let's show that if a has a multiplicative inverse,

then it is necessarily unique, okay?

This is actually easy, so if there are two different inverses,

denote them by x and y, then we can write the following set of equations.

So first of all x is equal to x times 1.

1 is just a times the inverse of a, which is y, right?

Now we have two multiplications, and let's perform them in a different order.

Let's just multiply x by a, and

this is again 1 just because x is also a multiplicative inverse times y.

And this is y, so what we've proved just Is that x is equal to y.

So if there are two multiplicative inverses of a modulo n,

then they are equal, okay?

Now the question is when there is a multiplicative inverse of a modulo n.

And the simple answer is that,

it exists whenever the greatest common divisor of a and n is equal to 1, okay?

So this is a simple criteria of the existence

of the multiplicative inverse of a modulo n.

So let's prove this.

So first of all, the fact that ax is congruent to 1 modulo n actually

is equivalent to the fact that ax + kn is equal to 1 to some integer k, right?

So it just means that ax- 1 is divisible by n.

So there is some number k such that ax- 1 is equal to kn, some integer k, okay?

On the other hand this can be considered as a Diophantine equation with

these two coefficients, a and n.

And we know that there exist a solution for this Diophantine equation if and

only if the greatest common divisor of a and n divides 1.

So in our terms, this is c and we have a and n as coefficients.

And the greatest common divide of these two coefficients should divide c.

So c is 1 in this case.

So for the greatest common divisor, there is no choice, so it should be equal to 1.

So the only number that divides 1 is equal to 1, which proves the theorem, okay?

So now we know that the reason there is a multiplicative inverse of a and n, and

if and only if the greatest common divisor of a and n is equal to 1.

This actually also shows why there is no multiplicative inverse

of 3 modulo 6 in particular, okay?

Now so what this tells us is that if the greatest common divisor of a and

n is equal to 1, then there is a multiplicative inverse of a modulo n.

And this in particular means that we can divide by a modulo n.

And we can actually do this algorthimatically.

We can implement an efficient procedure for doing this.

So given numbers a, b, and n,

we would like to find the number of x, such that ax is equal to b modulo n.

That is we would like to divide b by a.

So to find a solution to such an equation, to find such an x,

we can do the following.

First given a and n, we use the extended Euclid's

algorithm to represent a as a linear combination of a and n.

So it gives us the following two coefficients, t and s.

So nt + as is equal to 1, so this means,

it means exactly that s is a multiplicative inverse of a modulo n.

So indeed if you multiply a by s you get 1 modulo n, right?

So because as plus something divisible by n is equal to 1, so

the remainder of as is equal to 1 modulo n.

So s modulo n to be more precise

is the multiplicative inverse of a modulo n.

Now it remains just a multiply b with s.

Namely recall that just dividing by a is the same as

multiplying with multiplicative inverse of a modulo n.

And as we've just discussed,

it can be found by the extended Euclid's algorithm, okay?

Now let me conclude with a toy example.

So assume that we would like to divide 7 by 2 modulo 9.

First of all, we can do this just because the greatest common divisor of 9 and

2 is equal to 1.

So since it is equal to 1, it can be represented using the extended

Euclid algorithm as a linear combination of 9 and 2.

So in this particular case,

1 is equal to 9 times 1 + 2 times -4, okay?

This tells us that -4 is a multiplicative inverse of 2 modulo 9.

So -4 is actually 5 modulo 9, okay?

Which means if you divide 7 by 2 modulo 9,

it is sufficient to multiply 7 by 5 modulo 9.

When we multiply 7 by 5 modulo 9, it gives us 8,

which means that 7 divided by 2 is equal to 8 modulo 9.

So let's check it.

Indeed, if we multiply 8 by 2, it gives us 16, and that is indeed 7 modulo 9.

So indeed 8 is equal to 7 divided by 2 modulo 9.

So what we've just presented is an efficient procedure for

division modulo n and for computing inverses modulo n.

And this is an essential step of modern systems like Euclid,

which we will learn in the later lessons in this class.