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.