Euclidean Division: Integer Division with Remainders

In today’s post I want to talk about Euclidean division. This is a more general definition of division between two integers because, unlike regular division, it’s defined for any pair of integers (except when the divisor is 0). I originally wanted to cover this topic in my post on negative numbers. But I decided to take it out in a separate post in order to keep the length below some reasonable limit.

In the previous post on negative numbers and integers I gave you the intuition for generalizing the operations we were familiar with from natural numbers. I showed you how the four main operations (addition, subtraction, multiplication, and division) behave just like before, even when one or both numbers are negative. And also how their result is always another integer. Well, except for division.

I explained why division is left undefined for most pairs of integers and how it only works when the dividend happens to divide evenly into the divisor. This is an easily fixable problem, as you’ll see in the next post from my series on numbers and arithmetic. In particular, when we start considering fractional numbers. However, here I want to show you another way of dealing with it without the need for new number types.

The things I’m going to show you today are also going to be very helpful for a few other upcoming posts on number theory.

What is Euclidean division?

Euclidean division (also known as division with remainder) is a special type of division that returns two numbers. This is an early method used by the great Ancient Greek mathematician Euclid of Alexandria that we still use today (after some evolution).

I already gave you the basics of this method in my post on natural numbers. For example, say you and two of your friends want to divide 10 apples equally between the three of you. You can divide 9 of them into groups of 3 (the quotient) and the last apple will be the remainder. We can write this as:

   

How exactly did we find these values? Well, out of the 10 apples, we took 9 and split them into groups of 3, right? We took 9 because this is the largest number divisible by 3 that is still less than the dividend (10). Then, our quotient became 3 (because ) and our remainder became 1 (because ).

Now let’s formalize this procedure a little bit so we can generalize it to the whole set of integers.

How it works

Let’s consider any division , where D is the dividend and d is the divisor.

The idea is to to find the greatest integer less than or equal to D that is divisible by d without remainder (that is, with remainder equal to 0). The integers divisible by d are all in the form for an arbitrary integer k. And we call the k which satisfies this requirement the quotient (q). Then, we calculate the remainder, r, as .

This all sounds very abstract, so let’s see how it works in the example above:

Notice that the first five positive multiples of 3 (d) are marked. These are the products I was talking about. The dividend (10) is also marked and you see that it’s not one of those multiples. So, of all less than 10, we take the largest (9) as the temporary new dividend and find the quotient and remainder as:

   

   

To put it more formally, the result of the Euclidean division is two numbers, q and r, such that the following equality holds:

   

With the special requirement that is the greatest integer less than D. Notice that because , this requirement also ensures that r will always be either 0 (when D divides evenly into d) or a positive integer less than the absolute value of d:

   

Because if r were greater than |d|, we could increment the quotient by 1 by subtracting an additional d from D.

Here’s a few more examples:

   

   

   

   

Now let’s see how Euclidean division works when D or d (or both) are negative numbers.

Euclidean division with negative numbers

Let’s modify the first example above by making D negative:

   

We’re dividing a negative by a positive number, so we know the quotient will be negative. Therefore, this time we’re looking for the negative multiples of 3:

And here -12 is the largest integer divisible by 3 less than the dividend 10. Which means that the quotient and remainder are:

   

   

Therefore:

   

Notice that we took -12 (instead of -9) as the temporary dividend. In the negative direction, a smaller number means a larger absolute value, so the first number less than -10 is -12, not -9.

Here’s another modification of the example where this time the divisor is negative:

   

Again, because we’re dividing positive by negative, we know the quotient will be negative. But because the divisor is also negative (and the dividend is positive), we’re back at the positive side of the number line:

This time we’re making negative steps of -3, which is the same as making positive steps of 3. And the result of this division is:

   

Normally, when the remainder is 0, the result doesn’t change when we simultaneously switch the signs of the dividend and the divisor (e.g., ). Are you a little surprised that the results are different now? The same thing happens when both D and d are negative. To see how, let’s consider the final modification to our example:

   

We’re dividing negative by negative, so the quotient will be positive. This means we need to make positive steps in the negative direction, so we need the negative multiples of 3:

We made 4 steps, therefore:

   

Again, this is different from the result when we used the positive versions of D and d:

   

Even though the result would be the same if the remainder were zero. For example:

   

Well, if you think about it, all these results follow directly from the requirements we imposed on the quotient. Because we always choose a temporary dividend less than the real one, its absolute value may be different when we switch the signs. Consequently, the distance between the temporary and real dividend will also vary.

Anyway, for more intuition, let’s look at the examples from the previous section with small adaptations in the sign of the dividend or the divisor:

   

   

   

   

Negative remainders

Always taking the greatest integer less than the dividend is the main convention in mathematics. And it’s the most intuitive one, especially for positive integers. It turns out this isn’t the only convention, however. Some fields have alternative conventions for calculating the quotient in Euclidean division, while still respecting the constraints:

   

   

Since D and d are fixed, a different q will naturally lead to a different r. For example, what if we picked the smallest integer greater than the dividend as the temporary dividend (instead of the greatest integer less than the dividend)? Under this convention the remainder will always be negative. For example:

   

How did we get this?

This time we picked 12 (instead of 9), as the temporary dividend and q and r are calculated as:

   

   

Here’s another example:

   

As a small exercise, try to figure out the quotient/remainder pairs for the divisions and under the negative remainder convention.

And here’s a few more examples (adapted from the earlier examples with positive remainder):

   

   

   

   

Finally, to complete the intuition, let’s look at the same examples but with negative dividends or divisors:

   

   

   

   

Take some time to think about these results and make sure you understand how we got each quotient/remainder pair. Personally, I find it intuitive to go through each equality and verify that it works by multiplying the divisor by the quotient and adding the remainder to the resulting product (and make sure the whole thing is equal to the dividend).

What does a negative remainder represent?

To get some intuition about negative remainders, let’s first consider the interpretation of positive remainders:

   

You can basically think of this result as saying “if we didn’t have 1 extra apple, we could have divided the 10 apples evenly into 3 groups of 3″.

Take a look at this short clip I made that illustrates this division intuitively:

For the same division, the negative remainder version gives:

   

In this context, you can interpret the result as saying “if we did have 2 extra apples, we could have divided the 10 apples evenly into 3 groups of 4″.

In other words, with positive remainders we’re framing things in terms of a “surplus“, whereas with negative remainders we’re framing them as “shortage“. But both essentially contain the same information.

Take a look at another short clip that shows the intuition behind negative remainders with the “anti-apple” object (that stands for -1) I introduced in my post on negative numbers:

Now, I’m not aware of an existing convention to always take the negative remainder. However, especially in computer science, there are other conventions for calculating the quotient. These conventions may yield positive or negative remainders, depending on the signs in the specific dividend/divisor pair.

Alternative conventions for calculating the quotient

As we know by now, in any Euclidean division where the remainder is not zero, we have two choices for it: one is positive and the other is negative. The constraint is that the absolute value of the remainder must be less than the absolute value of the divisor. Like I said, the most common convention in mathematics is to always choose the positive remainder. But this isn’t the only one.

Across programming languages (and some areas in mathematics) there are four main alternative conventions for calculating the quotient. I could describe the calculation methods directly, but I will leave that for the next post of my series on numbers, since a new number type is necessary to properly understand them. Instead, for now I’m going to describe them only in terms of the effects they have on the sign of the remainder.

Here are the four types:

1. Floored division: always choose the remainder which has the same sign as the divisor.
2. Ceiled division: always choose the remainder which has a different sign from the divisor.
3. Rounded division: always choose the remainder with the least absolute value.
4. Truncated division: always choose the remainder which has the same sign as the dividend.

In this context, standard Euclidean division (which always returns the positive remainder) can be defined as “perform floored division if the divisor is positive and ceiled division if it’s negative”.

In principle, it doesn’t really matter if you place the constraint on the quotient or the remainder. The two are connected and picking a definition for one automatically specifies the other.

If you’re a programmer, most likely you already know which of these conventions your programming language follows. Well, to see how it fits into the big picture, here’s a table that summarizes the results of all conventions under the different scenarios we considered earlier involving :

Are there other conventions?

You might be wondering about the existence of three other (hypothetical) conventions. Can’t we have a convention that specifies to always pick the:

• negative remainder?
• remainder with the greatest absolute value?
• remainder which has a different sign from the dividend?

I personally haven’t come across either of these and they don’t sound very practical. My guess is that generally they aren’t used very often, except possibly in some special mathematical or software applications.

Still, for completion purposes, here’s a table that shows the type of results each hypothetical convention would produce. Compare it to the table above.

Divisibility at a glance

The last topic I want to cover today is about a few rules of thumb for quickly determining divisibility between integers.

We say that a number D is divisible by a number d if the Euclidean division gives a remainder of 0. According to this definition, 8 is divisible by 2 but not by 3.

Like I already showed you, if the remainder of a particular division is 0, changing the sign of either the dividend or the divisor will still give a remainder of 0 (and only possibly change the sign of the quotient). For this reason, I’m only going to consider the rules for natural numbers because they immediately generalize to integers.

The most direct way of checking divisibility is to actually perform the division and see if the remainder is 0. However, there are techniques that allow you to do this much faster for some divisors. For example, it’s very easy to check if a number D is divisible by 2, 3, or 5, even for very large D. It’s also easy to establish divisibility by 4, 6, 8, 9, and 10 (those patterns mostly follow from the previous ones). The rule for divisibility by 7 is a little trickier and I personally don’t use it too often, since I don’t find it particularly faster than just checking manually. For the same reason, I generally don’t bother remembering divisibility rules for numbers larger than 10 (with some exceptions).

Below, I’m going to show you what some of these rules are, along with a few examples for each. For now, I’m just giving you the rules without proofs (which I’m going to show you in my post on modular arithmetic). There’s more than one rule for some numbers, but here I’m only giving you the most popular and convenient ones.

Divisibility by 2, 4, and 8

Тhe most basic divisibility rule says that a number n is divisible by 2 if and only if its last digit is divisible by 2. For example, 2393848 is divisible by 2 because the last digit (8) is divisible by 2. And 209191 is not divisible by 2 because the last digit (1) isn’t either. In other words, as long as the last digit is 0, 2, 4, 6, or 8, the whole number is divisible by 2. And that’s all there is to it!

What about divisibility by 4? Here the rule is very similar, except we need to check the last 2 digits. The rule says that a number n is divisible by 4 if and only if the number formed by its last 2 digits is divisible by 4. For example, 123989832120 is divisible by 4 because 20 is divisible by 4. And 213989818 is not divisible by 4 because 18 isn’t either.

Finally, the rule for divisibility by 8 is identical, except now you need to check the number formed by the last 3 digits. If that number is divisible by 8, then so is the original number. For example, 32819023800 is divisible by 8 because 800 is divisible by 8. And 2130888701 is not divisible by 8 because 701 isn’t either.

As you can see, these rules allow you to check divisibility for arbitrarily large numbers. They reduce the test for divisibility of any number n by 2, 4, and 8 to only testing the number formed by n‘s last 1, 2, or 3 digits (respectively).

Divisibility by 5 and 10

The divisibility rule for 5 is one of the simplest. A number n is divisible by 5 if and only if its last digit is 0 or 5. For example, 21398792130 and 2132135 are both divisible by 5, whereas 128983 and 20907 are not.

And the divisibility rule for 10 is even simpler. A number is divisible by 10 if and only if it’s divisible by both 2 and 5. Well, to be divisible by 5, its last digit must be 0 or 5. And to be divisible by 2 its last digit must be 0, 2, 4, 6, or 8. And since 0 is the only number that’s common in both lists, from this we conclude that a number is divisible by 10 if and only if its last digit is 0.

Divisibility by 3, 6, and 9

The divisibility rules for 3, 6, and 9 are slightly different because this time you need to look at all the digits. More specifically, you need to take the sum of all digits.

The first rule says that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. For example, you can immediately tell that 906 is divisible by 3 because and 15 is divisible by 3. And 1055 is not divisible by 3 because and 11 is not divisible by 3.

Sometimes you might need to apply the rule more than once, if the original number is too large. For example, the sum of digits of 89799787869779982 is 129 but it’s not immediately obvious if 129 itself is divisible by 3. But then, using the rule on 129 gives us and because 12 is divisible by 3, we can infer that 89799787869779982 is also divisible by 3.

As for the second rule, a number is divisible by 6 if and only it’s divisible by both 2 and 3. This rule is very similar to the divisibility rule by 10, with the test for divisibility by 5 replaced with divisibility by 3. This means that the number’s last digit has to be divisible by 2 and the sum of its digits has to be divisible by 3.

Finally, the rule for divisibility by 9 is identical to the 3 rule. Except, here the requirement is that the sum of digits is divisible by 9. For example, we can immediately tell that 513 is divisible by 9 because and 9 is divisible by 9. Similarly, we can immediately tell that 7144 is not divisible by 9 because and 16 is not divisible by 9.

Divisibility by 7

Here, the rule is to basically truncate the first digit from the number, multiply it by 2, and subtract it from the remaining number. If the result is divisible by 7, then so is the original number. In other words, a number is divisible by 7 if and only if the number resulting from subtracting twice the first digit from the remaining digits is divisible by 7.

For example, with this rule we can immediately tell that 161 is divisible by 7. That’s because and 14 is divisible by 7. Similarly, we can tell that 394 is not divisible by 7 because and 31 is not divisible by 7.

Similar to testing for divisibility by 3 or 9, you sometimes might have to apply the rule more than once, if the first time doesn’t produce a short enough result. For example, if you had to test if a number like 6391 is divisible by 7, you could do:

   

   

We finally reached a number we recognize as a multiple of 7 (because ), so we know that 6391 is divisible by 7.

Like I said earlier, I personally don’t use this rule very often because it’s not as easy to apply as the other rules. Not that the steps themselves are difficult… But if there are too many digits, you might need to keep track of a lot of results in your head (which is also prone to errors). But the rule still comes in handy when working with numbers up to 6-7 digits long.

Divisibility by numbers larger than 10

I’m not going to go into too much detail here, but I wanted to have this section for completion purposes.

In principle, you can derive divisibility rules for any number. However, as the numbers get larger, the rules become less practical. Not to mention that keeping them in your memory is not very practical by itself. And, at some point, just performing regular Euclidean division becomes way easier.

However, certain rules are still easy to apply and you don’t even have to put any special effort in memorizing them. Particularly, when the number is a product of two numbers for which we already have a divisibility rule. This is in the spirit of the rules for 6 and 10 where we infer that a number is divisible by 6 if it’s divisible by both 2 and 3 and divisible by 10 if it’s divisible by both 2 and 5. That’s because:

   

   

This means that we can easily derive rules for numbers like 12, 14, 15, 18, and 20:

• 12: divisible by 3 and 4
• 14: divisible by 2 and 7
• 15: divisible by 3 and 5
• 18: divisible by 2 and 9
• 20: divisible by 4 and 5

Let me also give you an example of a divisibility rule for a two-digit number which doesn’t have any smaller factors. A number is divisible by 11 if and only if the alternating sum of its digits is also divisible by 11. This rule is very similar to the rules for 3 and 9. But, instead of adding all digits, you take turns between addition and subtraction.

For example, the number 878273 is divisible by 11 because:

   

Because subtraction is involved, here you sometimes might end up with a negative number as a result of this alternating sum. But that’s not a problem! As long as the resulting number leaves a remainder of 0 when divided by 11, the original number is guaranteed to also be divisible by 11.

Summary

In a nutshell, Euclidean division is a way of performing division between any pair of integers, intended to generalize this operation by introducing the concept of a remainder. For any dividend/divisor pair , Euclidean division returns two numbers: q (the quotient) and r (the remainder), such that the following constraints are satisfied:

   

   

I also told you that, whenever r is not 0, we have two choices that respect these constraints — positive and negative. And each of those are associated with two different quotients, exactly one number apart.

The main convention in number theory (and mathematics in general) is to always pick the positive remainder. But I also showed you four alternative conventions for the sign of the remainder (mainly used in areas related to computer science):

1. Floored division: same sign as the divisor
2. Ceiled division: different sign from the divisor
3. Rounded division: least absolute value
4. Truncated division: same sign as the dividend

In the final section, I focused on the cases where the remainder is 0. More specifically, on the so-called divisibility rules which allow you to easily determine if the remainder will be 0 for specific dividend/divisor pairs. These divisibility rules focus on the divisor and here’s a summary of the most important ones:

• 2: last digit must be divisible by 2
• 3: sum of digits must be divisible by 3
• 4: last two digits must be divisible by 4
• 5: last digit must be 0 or 5
• 6: must be divisible by 2 and by 3
• 7: twice the first digit subtracted from the rest must be divisible by 7
• 8: last three digits must be divisible by 8
• 9: sum of digits must be divisible by 9
• 10: last digit must be 0

Anyway, hopefully you found today’s topic easy to follow. The intuition you gained will be very helpful for understanding more advanced concepts in some of my upcoming posts. As always, if you had any difficulties in following this post, leave a comment below!