0:00

[SOUND] Hi, I'm Vladimir Podolskii.

And today we're going to discuss modular arithmetic.

Let's start with following toy problem.

What is the remainder of 17 times 12 times

19 + 5- 23 when we divide it by 3?

Okay, so this is not a complicated problem,

we can just compute this number and find the remainder when we divide it by 3.

There's nothing that's complicated here.

But let's ask the following question.

Do we actually need to do this computation?

So the computation of this number will take us some time.

Do we actually need to do this computation?

And is there probably a better way to do it, or just simpler and better way?

And it turns out that there is.

And to do this, we need to study remainders a little bit more.

So first we will introduce, congruence relations.

We say that two numbers, a and b are congruent modulo m,

if they have the same remainder when we divide them by m.

So we write this in the following way.

Okay, let's discuss this new definition notes that we have discussed before,

that two numbers in because, have the same remainder if we divide them by m,

if and only if their difference is divisible m.

So equivalently, we can see that a is congruent to b modulo m,

if a- b is divisible by m.

And note now that each numbers are congruent to modulo m.

These are all numbers, because the form a + k times m for some integer k.

So note these are exactly the numbers, such that if you subtract a from

a plus k times m, then the result will be divisible by m.

So all numbers that are congruent to a modulo m forum a plus k times m.

And in particular, if r is a reminder of a then divide it by m,

then a is congruent to r modulo m.

So a is always congruent to its remainder modulo some number m.

2:57

Okay, while this is true, and indeed congruence of a and

b modulo m means that m divide a- b.

But note that if you consider a + c and b + c,

then the difference of these two numbers is the same as the difference of a and b.

So a + c- b + c is the same as a- b.

So, if m divides a- b, then m divides a + c- b + c is just the same number.

So a + c and b + c, then are also congruent to modulo m.

Okay, and this rule can be easily extended.

3:35

Now if you have two congruences, a is congruent to b modulo m and

c is congruent to d modulo m, then a + c is congruent to b + d modulo m.

In other words, congruence is preserved under addition.

If you take two congruences and we add them, and

the left parts of the congruences and

the right part of the congruences, then the result will be also congruent.

The results of this additions.

Okay, how can we prove it?

It turns out that proof is very simple using the previous rule.

We can just do it in two steps.

We can consider a + c and first substitute c by d,

and on the second step you will substitute b by d.

Variable for these equations are these congruence are true.

4:25

So here they just release in two separate lines.

Note that both of them are applications of the previous property.

So in the first one, we have that c is congruent to d modulo m.

And we just add some number a to both parts, and so the congruence is preserved.

And then the second part, a is congruent to b modulo m, this is given to us.

So we add d to both parts, and so

now we have a + d is also congruent to b + d modulo m.

So overall we have that a + c is congruent to b + d modulo m,

and this is exactly what we need.

So congruence is preserved on the ridge.

5:07

Okay, and now we can even these two simple observations can be used to solve some

simple problems, so let's consider the following problem.

Suppose we have sum of several numbers, 14, 41, 20, 13, 29.

And the question is: is the sum divisible by 4?

And actually, what is the remainder of this sum when we divide it by 4?

Okay, of course, we can compute the sum of these numbers and

see what is the remainder of this number when we divide it by 4, but

we do not have to do the calculation.

Instead, we can apply the results that we just obtained.

What we can do instead, we can find the remainder modulo 4,

such that it is congruent to our sum.

So we can just trade our sum, and now using our rules,

we can substitute each summoned by a congruent number.

And let's just substitute each number by the remainder of this number when we

divide them by 4.

So 14 is 12 + 2.

So 12 is divisible by 4, so 2 is congruent to 14 modulo 4.

6:23

And 1 is congruent to 41 modulo 4, because the difference is 40 and

40 is divisible by 4, 0 is congruent to 20 modulo 4, 20 is just divisible by 4.

1 is congruent to 13 modulo 4 and

1 is congruent to 29 modulo 4, 28 is divisible by 4.

So 29- 1 is divisible by 4, so 29 and 1 are congruent.

So if the sum of the results is, this is much simpler than just sum up the original

numbers then we obtain 5, and 5 is congruent to 1 modulo 4.

So our original expression is congruent to 1 modulo 4, and

so 1 is the remainder of our general expression modulo 4.

So now, this are not all properties of congruences we can actually prove.

We can do basically the same with multiplication.

So suppose a is congruent to b modulo some number m.

Then a times c is congruent to b times c modulo the same number m for

any constant c, for any integer c, okay?

What does it mean?

It means, that if you multiply two congruent numbers by the same number,

the results are still congruent.

Any why?

Is this true?

Indeed, congruence of a and b means that m divides a- b.

7:55

So we have this rule.

And it can be easily extended if we have two congruences.

So we have a is congruent to b modulo m, and that c is congruent to d modulo m.

Then a times c is congruent to b times d modulo m.

In other words, congruence is preserved under multiplication.

If you have two congruences, a is congruent to b and c is congruent to d,

both modulo m, then product of left parts of these congruences

is congruent to products of right parts of these congruences.

Okay, and the proof is just like for addition.

We can first substitute c by d and then substitute a by b.

Again, let's write down both of these congruences separately,

and note that here we just apply the previous property twice.

In the first part, we have a congruence of c and d, given that c is congruent d

modulo b, and we multiply them both parts by sum number e.

And in the second congruence we have,

from the beginning that a is congruent to d modulo m.

This is given to us, and then we multiply this congruence by sum number d.

The congruence is preserved, so we have both of these congruences and

together they give us that a times c is congruent to b times d modulo m.

9:17

Okay, and now we are ready to solve the problem from the beginning of this lesson.

What is the remainder of this expression when we divided by 3?

And the idea here is that,

we can safely substitute all numbers in this expression by our congruent numbers.

And instead of numbers in this expression, we can substitute for

example the remainders of these numbers and

compute the expression, it is much simpler.

So the remainders here are 0, 1, and 2.

These are possible remainders modulo 3, and so

we can substitute all numbers by the remainders.

The remainder of 17 is 2, 15 is divisible by 2, so the remainder is 2.

12 is divisible by 3, 15 is divisible by 3, so

the remainder of 17 when we divide it by 3 is 2.

12 is divisible by 3, so the remainder is 0.

19 has the remainder 1, because 18 is divisible by 3,

and 19 is 18 + 1, and 5 has the remainder 2.

And in the end, 23 has the remainder 2, because 21 is divisible by 3.

And so, here it is already easy to compute the result and

find the remainder of this expression, but let's not do it.

Even this is too complicated.

We can actually simplify this even more and learn one more trick at the same time.

So observe that we can substitute these numbers by any congruent numbers we want,

not necessarily by 0, 1, and 2.

We can pick any number here in the original expression and

substitute by any congruent number modulo 3.

So let's just do the following.

We will use instead of number 0, 1, and 2 we will use 0, 1, and -1.

Observe that 2 is congruent to -1 modulo 3.

And so, then in the previous attempt

we just substitute all numbers 2 by -1 and the expression is even more simple.

This is not very useful when we do computations by 3, but

the same trick will be much more useful when we do computations modulo

some more large numbers.

But here, we have this expression -1 times,

in the break we have 0 times 1- 1 and plus 1 on the end.

So in the break we have -1.

So we have the first product is -1 times -1, which is 1, so

we have 1 + 1 which is 2.

So our original expression is congruent to 2 modulo 3.

And this is the remainder of our original expression modulo 3.

[SOUND]