[MUSIC] So division is not always possible. But we can generalize this notion to be applicable to all a and b. So suppose we have a positive integer b. And we will introduce division with remainder now. The result of the division of a by b with a remainder is a pair of integers q, which is called quotient, and r, which is called a remainder. Such that a is equal to q times b + r and r is nonnegative but is at most b. And note that, if r = 0, then b divides a. And note that this notion, this definition just turns out to be the definition of the fact that b divides a if r is equal to 0. Okay, now, what is the intuition behind this notion? So here is the definition again on the top of the screen. And the intuition is simple. So, and assume here, again, for simplicity that a is positive. So suppose we have a group of a objects and you would like to split it into some groups of size b. And now we can pick these groups of size b one by one. And if we do it, then in the end, we might have some number of objects left that are not enough to form one more group. And then this number of objects will be r, will be the remainder, and the number of groups we have formed will be q, the quotient. And so this formula will be exactly true. So we have q groups of size b, and we have additionally r objects left. And since r objects are not enough to form a new group, then r is less than b. So here's the intuition behind this definition. And let's consider some examples. For example, consider a = 15 and b = 4. Note that 15 doesn't divide 4. But still, it divides. So we can divide 15 by 4 with the remainder. 15 = 3 times 4 + 3. It can be easily checked. And then q = 3, and r is also equal to 3. Here is another example. We can apply division with remainder to negative numbers. If a is 13 and b is 3, then we have the following equality, -13=(-5) times 3, which is -15 + 2. And so q here is equal to -5 and r is equal to 2. And one more example. Consider a to be equal to 12, and b equals 4, then 12 is 3 times 4 + 0. And here the remainder r is 0, q is equal to 3, and a is divisible by b. So let's get some more intuition. How do numbers that give the remainder 1 when we divide them by 7 look like? Let's look at them, at the number line. So they all have the form a equals to q times 7, we divide it then by 7, plus 1, the remainder is 1. And q here is arbitrary integer number. It can be 0, 1, 2, 3 and so on, and minus 1, minus 2, minus 3, and so on. Okay, so which numbers have this form? So one simple example is for q = 0, then a = 1, well, here is 1. Now, we have a sequence of numbers for positive q. We have 7 plus 1, so for q equals 1, we have 2 times 7 plus 1 for q equals 2, which is 15. Then we have 22, and so on. Note that each next number is by 7 greater than the previous one. Finally, for -q, we have another sequence of numbers. For q = -1, we have -7 plus 1, which is minus 6. For q = -2 we have -2 times 7 + 1, which is -13. And then we have -20, and so on. So note that here again, each next number is smaller than the previous one by 7. So we have a sequence of numbers. And note that between two adjacent numbers the distance is 7. So each 7th number on the line has a remainder 1. And that's how we look like. And in general, if you consider the numbers that give some fixed remainder r when we divide them by b, then in general we have the form a = q times b + r for all possible q. And one example is for q equals 0, this is just the remainder itself is equal to r. And then we have a sequence for positive q, r + b, r + 2b, r + 3b, and so on. So each next number is greater than the previous one by b. Then we have a sequence for negative q, q = -1, -2, -3, and so on. And the sequence is r-b, r-2b, r-3b. Each next number is smaller by b than the previous one. And so again, the distance between adjacent numbers that give the remainder r when we divide them by b is b. And so each bth number has the remainder r. Let's discuss briefly why this is always possible, why we can always divide a by b with the remainder, why such q and r exists. And the intuition is simple. We have already mentioned that we can just do the following. We can take a group of a objects and we can form groups of size b one by one. And in the end we will be left with some amount of objects that is not enough to form a new group. And then the number of remaining objects is r and the number of groups is q, so intuition is simple. So we can restate it slightly more formally. So what we can do, we have a number r and we can subtract b from it. We can subtract it once again from the result, and so on. So we can repeatedly subtract b from our number, until we are left with a number which is less than b. And then the remainder will be r, the resulting number we are left with will be r and the number of subtractions we have made will be q. And know that r is less than b, because r is not enough to subtract b once again and to stay within nonnegative numbers. What happens if a is negative? So here in this intuition, in this explanation, a is positive. What happens if a is negative? It's also simple, just instead of subtracting b from a, just add b to a until we get a positive number. And then this positive number will be r, and the number of additions will be q. Now we have introduced the new notion, divisibility with the remainder. And there's a simple connection of this notion to the notion of divisibility. And here it is. If you have two integers a1 and a2 and they have the same remainder when we divide them by b, if and only if the difference is divisible by b. So here is the connection, and let's prove it. So suppose a1 and a2 have the same remainder. Then a1 = q1 times b + r, a2 = q2 times b + r. So let's consider the difference and note that the difference r and r cancel out. And the difference is q1 minus q2 times b. And just by definition, so we have the difference is b times some integer number. So just by definition, we divide the difference of a1 and a2. Okay, so in the other direction. Suppose b now divides the difference, a1 minus a2. Then this means that there is some k that a1 minus a2 is equal to k times b. And now it took us some remainder when we divided by b, so it has some form a2 = q1 times b + r for some r. And then we can substitute a2 into the first equality, and then we have that a1 = a2 + k times b. And then a1 is just equal to b times some number q1 + k + r. And this is exactly the form for division with remainder, and r here is the remainder. So the remainder of a2 when we divide a1, when we divide it by b is the same as the remainder of a2 when we divide it by b. [MUSIC]
