Math from the ground up: Euclidian Division

We talked about divisibility, but is this really all what it is to tell about division?! Of course, not! There are many situations (in fact, probably most situations) in which a certain number $b$ is not completely divisible by a certain number $a$. By this, I mean that $b$ cannot be distributed into $a$ equal groups with zero remainder. Consider, for instance, the case in which you have 27 apples that you want to distribute equally over 4 baskets. You can have groups of 1 apple with a remainder of 23 apples, groups of 2 apples with a remainder of 19 apples, groups of 3 apples with a remainder of 15 apples, groups of 4 apples with a remainder of 11 apples, groups of 5 apples with a remainder of 7 apples, or groups of 6 apples with a remainder of 3 apples. You cannot divide the 3 apples equally on 4 baskets and still keep them whole. When we said that the number $a$ divided the number $b$ and indicated that with the notation $a \mid b$, we meant that you could end up with zero remainder. That was the special case. The general case is that you end up with some remainder that may be zero. This is called ‘Euclidian division’ after the Greek mathematician Euclid, who lived more than 2000 years ago.

\[ \begin{array}{l|l|l|l|l} \text{Basket }1 & \text{Basket }2 & \text{Basket }3 & \text{Basket }4 & \text{Remainder} \\ 0 & 0 & 0 & 0 & 27\text{ apples} \\ 1\text{ apple} & 1\text{ apple} & 1\text{ apple} & 1\text{ apple} & 23\text{ apples} \\ 2\text{ apples} & 2\text{ apples} & 2\text{ apples} & 2\text{ apples} & 19\text{ apples} \\ 3\text{ apples} & 3\text{ apples} & 3\text{ apples} & 3\text{ apples} & 15\text{ apples} \\ 4\text{ apples} & 4\text{ apples} & 4\text{ apples} & 4\text{ apples} & 11\text{ apples} \\ 5\text{ apples} & 5\text{ apples} & 5\text{ apples} & 5\text{ apples} & 7\text{ apples} \\ 6\text{ apples} & 6\text{ apples} & 6\text{ apples} & 6\text{ apples} & \color{red}{3\text{ apples}\lt 4\text{ baskets}} \end{array} \]

But when we say ‘remainder,’ what do we mean exactly? In the previous example, we could divide 27 apples on 4 baskets in 7 different ways (one of them is to have no apples at all in each basket), and end up with some remainder. In mathematics, as we will always keep saying, it is essential that things have one and only one meaning to avoid ambiguity (lack of clarity.) One of those 7 cases mentioned above is different from all others. Can you tell which one? It is the last one with 6 apples in each basket and only 3 remaining. What makes it different from the other cases is that the remainder is less than the divisor (number of baskets,) so you cannot go one step further. This is the farthest you can go. As a matter of fact, all cases of division can be shown to either reach this stage where the remainder is less than the divisor, or have zero remainder (which is also less than the divisor.)

The previous concept is expressed as:

\[ \cssId{equation4.1}{ \begin{equation} \tag{4.1} \color{blue}{ \text{For } d,n,q,r \in \mathbb{Z}^+_0; \quad d \neq 0 \\ n \div d = (q, r) \equiv n = d \times q + r; \quad 0 \le r \lt d } \end{equation} } \]

Q.E.D.

The notation $(q,r)$ is called an ‘ordered pair.’ An ordered pair in mathematics is a pair of numbers, each of which has a certain defined meaning based on its ‘order of writing.’ This means that the first number will always mean something in particular, and the second will always mean something in particular. In the case of division, the first number in the ordered pair means the quotient of division, and the second number means the remainder of division. So, using this notation, we write $27 \div 4 = (6,3)$, which is equivalent to (the sign $\equiv$) the equation $27=4 \times 6 + 3$.

\[ \begin{aligned} & \text{For } n \in \mathbb{N}; \quad a,b,q_n,r_n \in \mathbb{Z}^+_0; \quad a \neq 0 \\ & b \div a = (q_1,r_1) \equiv b = a \times q_1 + r_1 \\ & 0 \le r_1 \lt a \implies \mathbf{Q.E.D.} \\ & \text{Repeat with: } \\ & q_2 = q_1 + 1 \iff q_1 = q_2 - 1 \\ & r_2 = r_1 - a \iff r_1 = r_2 + a \\ & \begin{aligned} b & = a \times q_1 + r_1 \\ & = a \times (q_2 - 1) + (r_2 + a) \\ & = [a \times (q_2 - 1) + a] + r_2 \quad \text{from } \href{http://math-from-the-ground-up.blogspot.ca/2016/09/addition-and-subtraction.html#equation1.1}{1.1} \\ & = [a \times (q_2 - 1 +) + a \times 1] + r_2 \quad \text{from } \href{http://math-from-the-ground-up.blogspot.ca/2016/09/multiplication.html#equation2.6}{2.6} \\ & = a \times (q_2 - 1 + 1) + r_2 \quad \text{from } \href{http://math-from-the-ground-up.blogspot.ca/2016/09/multiplication.html#equation2.11}{2.11} \\ & = a \times q_2 + r_2 \end{aligned} \\ & 0 \le r_2 \lt a \implies \mathbf{Q.E.D.} \\ & \text{Repeat with: } \\ & q_3 = q_2 + 1 \\ & r_3 = r_2 - a \end{aligned} \]

The acronym Q.E.D. stands for ‘quod erat demonstrandum,’ which is latin for ‘that which was to be demonstrated.’ In mathematics, if we are to prove something, when we reach the end of the proof we write Q.E.D. to indicate the end. In the previous example, if $r_1$ (the remainder) is less than $a$ (the divisor,) then we have demonstrated that there exists a number $q_1$ such that $b = a \times q_1 + r_1$ and $0 \le r_1 \lt a$. If that was not the case, then we continue the calculations with the value of $q_2 = q_1 + 1$ (i.e. we increase the value of the quotient by 1) and $r_2 = r_1 - a$ (i.e. we decrease the value of the remainder by as much as $a$.) Rearranging and substituting results in another equation with $q_2$ instead of $q_1$ and $r_2$ instead of $r_1$, and the cycle is repeated for those new values $q_2$ and $r_2$. Eventually, there must exist two numbers that satisfy the definition of Euclidian division $\href{#equation4.1}{4.1}$.

Negative integer division

But what about integer division that includes negative numbers? According to definition $\href{#equation4.1}{4.1}$, division is defined in terms of multiplication. We know from $\href{http://math-from-the-ground-up.blogspot.ca/2016/09/multiplication.html#equation2.8}{2.8}$ that multiplication extends to integers, positive and negative. Hence, division also extends the same way, since it is defined in terms of multiplication. But something funny happens when we try to apply definition $\href{#equation4.1}{4.1}$ to negative numbers. Consider the case in which a debt of $\$100$ is to be divided equally among $8$ debtors. Since it is a debt, we can consider it a negative number, because we said before that negative numbers were originally a way of expressing debt. This means we want to evaluate $-100 \div 8$. If we distribute $\$1$ of debt on each of the debtors, we will end up with a remaining debt of $\$92$; in other words, a remainder of $-92$, which is smaller than the divisor! Any negative number is smaller than any positive number. So, definition $\href{#equation4.1}{4.1}$ does not give us a unique case in which the remainder is less than the divisor. In this particular example, there are 14 different cases in which the remainder is less than the divisor; namely the ordered pairs $(0,-100)$, $(-8,-92)$, $(-16,-84)$, $(-24,-76)$, $(-32,-68)$, $(-40,-60)$, $(-48,-52)$, $(-56,-44)$, $(-64,-36)$, $(-72,-28)$, $(-80,-20)$, $(-88,-12)$, $(-96,-4)$, $(-104,4)$. However, the last of these solutions is still unique among the others. It is the only solution with a positive value that is less than the divisor. This gives us a chance to come up with a definition of Euclidian division that applies to all integers.

\[ \cssId{equation4.2}{ \begin{equation} \tag{4.2} \color{blue}{ \text{For } n,d,q,r \in \mathbb{Z}; \quad d \neq 0 \\ n \div d = (q,r) \equiv n = d \times q + r; \quad 0 \le r \lt |d| } \end{equation} } \]

How is $\href{#equation4.2}{4.2}$ different from $\href{#equation4.1}{4.1}$? Try to have a close look at both of them and see for yourself. Definition $\href{#equation4.2}{4.2}$ has $\mathbb{Z}$ instead of $\mathbb{Z}^+_0$, which means it extends the definition to all integers. The second difference is that the final inequality that defines the unique case for the remainder uses $|d|$ instead of just $d$. The use of the absolute value of the divisor guarantees that the unique case is selected where the remainder is both positive and less than the divisor. This is called the ‘least positive remainder’ method, and it is by far the most common method of performing integer division. As a matter of fact, it is the default (presumed) method if nothing else is stated. The reader can investigate the case in which the divisor is negative and the dividend is positive to see that the only unique ordered pair of quotient and remainder is that in which the remainder is positive and less than the divisor.

The ‘least positive remainder’ method of division is the most common method.

What would really be the number of possible ordered pairs that satisfy definition $\href{#equation4.2}{4.2}$ for Euclidean division had the ‘least positive remainder’ method not been used? In the previous two examples of Euclidian division, our perception of the number of possible ordered pairs may have been subconsciously limited by the analogies we used. For the division of apples on baskets, we would not have thought of ‘borrowing’ more apples to divide on the baskets! For the distribution of a debt on debtors, we would not have though of giving them ‘more debt!’ But these are two things that can happen quite freely in the world of abstract (non-physical) numbers. Now consider the cases of dividing $23$ by $6$ (shown below on the left) and $-23$ by $6$ (shown below on the right.) In each of these cases, and indeed in all cases of Euclidian division, we can show that there is an infinite number of ordered pairs that would satisfy definition $\href{#equation4.2}{4.2}$ had the method of ‘least positive remainder’ not been used.

\[ n \div d = (q,r) \\ \begin{array}{cc|cc} \hline n = d \times q + r & 23 \div 6 & -23 \div 6 & n = d \times q + r \\ \hline \vdots & \vdots & \vdots & \vdots \\ 23 = 6 \times -5 + 53 \quad & (-5, 53) & (-5, 7) & \quad -23 = 6 \times -5 + 7 \\ 23 = 6 \times -4 + 47 \quad & (-4, 47) & \color{blue}{(-4, 1)} & \quad -23 = 6 \times -4 + 1 \\ 23 = 6 \times -3 + 41 \quad & (-3, 41) & (-3, -5) & \quad -23 = 6 \times -3 - 5 \\ 23 = 6 \times -2 + 35 \quad & (-2, 35) & (-2, -11) & \quad -23 = 6 \times -2 - 11 \\ 23 = 6 \times -1 + 29 \quad & (-1, 29) & (-1, -17) & \quad -23 = 6 \times -1 - 17 \\ 23 = 6 \times 0 + 23 \quad & (0,23) & (0, -23) & \quad -23 = 6 \times 0 - 23 \\ 23 = 6 \times 1 + 17 \quad & (1, 17) & (1, -29) & \quad -23 = 6 \times 1 - 29 \\ 23 = 6 \times 2 + 11 \quad & (2, 11) & (2, -35) & \quad -23 = 6 \times 2 - 35 \\ 23 = 6 \times 3 + 5 \quad & \color{blue}{(3, 5)} & (3, -41) & \quad -23 = 6 \times 3 - 41 \\ 23 = 6 \times 4 - 1 \quad & (4, -1) & (4, -47) & \quad -23 = 6 \times 4 - 47 \\ \vdots & \vdots & \vdots & \vdots \end{array} \]

Operator precedence revisited

We discussed before that the consensus on operator precedence is to do multiplication before addition and subtraction. What about Euclidian division (or, indeed, division in general)? Division takes the same precedence as multiplication in mathematical expressions. So, as far as we have discussed, parenthesized expressions take the highest precedence, followed by multiplication and division equally, followed by addition and subtraction equally. Therefore, expressions like $-48 \div 4 + 2$ are evaluated with division done first, so we evaluate the previous expression as $(-48 \div 4) + 2 = -12 + 2 = -10$ and not as $-48 \div (4 + 2) = -48 \div 6 = -8$.

The unique solution

Definition $\href{#equation4.2}{4.2}$ for Euclidian division also implies that there exists only one ordered pair that satisfies that division for any given integers $n$ and $d$. We can prove this by contradiction. We will examine the possibility that there exist more than one (at least 2) such ordered pairs, and we will see where this will take us. Let us assume that there are two different ordered pairs $(q_1, r_1)$ and $(q_2, r_2)$ for any given integers $n$ and $d$. This means that:

\[ \text{For } n,d,q_1,q_2,r_1,r_2 \in \mathbb{Z}; \quad d \neq 0; \\ (q_1,r_1) \neq (q_2,r_2) \tag{*} \\ n \div d = (q_1,r_1) \equiv n = d \times q_1 + r_1; \quad 0 \le r_1 \lt |d| \\ n \div d = (q_2, r_2) \equiv n = d \times q_2 + r_2; \quad 0 \le r_2 \lt |d| \\ \]

If both $r_1$ and $r_2$ are non-negative integers less than $|d|$, then the difference between those two numbers must also be less than $|d|$. Whether $r_1$ or $r_2$ is bigger we don't know, but regardless of that, the value $|r_2-r_1|$ or $|r_1-r_2|$ will be less than $|d|$, because $r_2-r_1=-(r_1-r_2)$ as stated in $\href{http://math-from-the-ground-up.blogspot.ca/2016/09/addition-and-subtraction.html#equation1.4}{1.4}$, and the absolute value gets rid of the sign as stated in $\href{http://math-from-the-ground-up.blogspot.ca/2016/09/addition-and-subtraction.html#equation1.6}{1.6}$.

\[ |r_2-r_1| = |r_1-r_2| \lt |d| \tag{**} \]

But because both equations (for the different ordered pairs) have $n$ as their left-side value, their right-side values are equal to each other. By subtracting $d \times q_1$ and $r_2$ from both sides of the equation that results (see below), we get:

\[ d \times q_1 + r_1 = d \times q_2 + r_2 \\ \cancel{d \times q_1} \color{red}{- \cancel{d \times q_1}} + r_1 \color{red}{- r_2} = d \times q_2 \color{red}{- d \times q_1} + \cancel{r_2} \color{red}{- \cancel{r_2}} \\ r_1 - r_2 = d \times q_2 - d \times q_1 \\ r_1 - r_2 = d \times (q_2 - q_1) \quad \text{from } \href{http://math-from-the-ground-up.blogspot.ca/2016/09/multiplication.html#equation2.11}{2.11} \\ |r_1 - r_2| = |d \times (q_2 - q_1)| \] \[ |r_1 - r_2| = |d| \times |(q_2 - q_1)| \quad \text{from } \href{http://math-from-the-ground-up.blogspot.ca/2016/09/multiplication.html#equation2.13}{2.13} \tag{***} \]

If $q_1 = q_2$ then $|q_2-q_1|=0$. Consequently, $|r_1-r_2|=0$, which means that $r_1 = r_2$. This conflicts with the initial assumption (*) that $(q_1,r_1)$ is different from $(q_2,r_2)$. If $q_1 \neq q_2$, and because both $q_1$ and $q_2$ are integers, the difference between them must also be an integer. Therefore, the value $|(q_2 - q_1)|$ must be an integer greater than zero. Hence, multiplying this positive value $|(q_2 - q_1)|$ by another positive value $|d|$ will result in a positive value that must be greater than or equal to the $|d|$. This means that $|r_1-r_2| \ge |d|$, which contradicts (**).

\[ |q_2-q_1| \ge 0 \quad \text{from } \href{http://math-from-the-ground-up.blogspot.ca/2016/09/addition-and-subtraction.html#equation1.6}{1.6} \\ \begin{array}{l|l} |q_2-q_1| = 0 & |q_2-q_1| \gt 0 \\ q_2 = q_1 & q_2,q_1 \in \mathbb{Z} \\ |r_1 - r_2| = |d| \times 0 \quad \text{from }(***) & \therefore |q_2-q_1| \ge 1 \\ |r_1 - r_2| = 0 & |(q_2 - q_1)| \color{red}{\times |d|} \ge 1 \color{red}{\times |d|} \\ r_1 = r_2 \large{\unicode{x21af}} & |r_1 - r_2| \ge |d| \quad \text{from } (***) \large{\unicode{x21af}} \end{array} \]

The symbol $\unicode{x21af}$ means ‘contradiction’ in mathematics, and we use it here to indicate that, assuming there was two different ordered pairs that satisfied definition $\href{#equation4.2}{4.2}$, this would lead us to the conclusion that either the two pairs are indeed equal to each other (left side above), or that some value is simultaneously (at the same time) smaller than and greater than or equal to another value (right side above)! In other words, there cannot be two different ordered pairs to satisfy the definition of Euclidian division. There is only one unique ordered pair for any given numbers $n$ and $d$.

Properties of division

It can easily be shown that division is not commutative, just by giving an example in which commutativity does not apply. We did that with divisibility in the previous article.

Like subtraction, the consensus is to evaluate division from left to right. Therefore, division is left-associative, just like what was discussed in talking about subtraction.

It is also left as an exercise for the reader to find an example in which division cannot be distributed on addition and subtraction, contrary to the case with multiplication.

Because the number 1 is the multiplicative identity element, and division is defined in terms of multiplication, the number 1 is also the identity element as a divisor. Any number can be divided by 1, resulting in the same number and zero remainder. This was discussed in $\href{http://math-from-the-ground-up.blogspot.ca/2016/09/division-divisibility.html#equation3.6}{3.6}$ while talking about divisibility.

Euclidian division as defined in $\href{#equation4.2}{4.2}$ is closed on integers. Dividing any integer $n$ by any non-zero integer $d$ will always result in an integer quotient $q$ with an integer remainder $r$.

More about division

So far, we have talked about integer division; that's why we had an integer quotient and an integer remainder. But is that all about division? Any preschooler can tell you that you can divide things into ‘fractions.’ Fractions constitute another category of numbers that is much wider than integers, just like integers constitute a wider category than natural numbers. We will talk about fractions in a later article, at which time we will explore more properties of division, in addition to the properties of fractions themselves. But just like we talked about divisibility first, then about division, we will talk next about something that will make discussing fractions easier: prime numbers.

‘Math from the ground up’ by Rafeek Mikhael licensed under Creative Commons Attribution-NonCommercial-ShareAlike International 4.0 license Creative Commons License .