In Definition 1.31 we had defined multiplication as repeated addition. For positive integers we conducted division as repeated subtraction. We first consider this case and then generalize the algorithm to all integers by giving a division algorithm for negative integers.
SubsectionDivision Algorithm for positive integers
In our first version of the division algorithm we start with a non-negative integer \(a\) and keep subtracting a natural number \(b\) until we end up with a number that is less than \(b\) and greater than or equal to \(0\text{.}\) We call the number of times that we can subtract \(b\) from \(a\) the quotient of the division of \(a\) by \(b\text{.}\) The remaining number is called the remainder of the division of \(a\) by \(b\text{.}\)
The division algorithm computes the quotient as well as the remainder. In Algorithm 3.6 and Algorithm 3.14 we indicate this by giving two values separated by a comma after the return.
If \(a\lt b\) then we cannot subtract \(b\) from \(a\) and end up with a number greater than or equal to \(b\text{.}\) Thus, in this case, the quotient is 0 and the remainder is \(a\) itself. We catch this case in step 1 of the algorithm.
As \(a=4\) and \(b=7\) statement \(a \lt b\) is true. So we follow the instruction after then and return the values of \(q\) and \(r\text{,}\) namely 0 and 4.
When working through the instructions of Algorithm 3.6 it can be more convenient to give the values of all relevant variables in each iteration of the loop in a table. We revisit Example 3.8 present the work in a more compact form.
In each row of the table we write the values of all variables for an iteration of the loop. If a variable has no value we leave the entry blank. Similarly in for the output we leave the entries of all variables that are not part of the output blank.
Sometimes one is not interested in both the quotient and the remainder. In such a case one can use a simplified algorithm. Determine the output of the algorithm in Checkpoint 3.12.
If \(a>0\text{,}\) then Algorithm 3.6 returns the quotient and remainder of the division of \(a\) by \(b\text{.}\) If we try to use Algorithm 3.6 when \(a\) is negative, the algorithm always returns \(0,a\) which does not satisfy the condition \(0\le r\) for the output since \(r=a\lt 0\text{.}\) So we need a different algorithm for the case \(a\lt 0\text{.}\)
When \(a\lt 0\text{,}\) we still want find \(q\) and \(r\) such that \(a=(q\cdot b)+r\) with \(0\le r\lt b\text{.}\) We get a positive remainder when \(a\) is negative by repeated addition of \(b\text{.}\) This is the same as repeatedly adding \(-b\text{.}\) Let \(s\) be the number of times we have to add \(b\) to \(a\) in order to get \(0 \le r \lt b\text{.}\) After \(s\) additions of \(b\) to \(a\) we have
If we let \(q:=-s\text{,}\) we get \(r=a-(q\cdot b)\) (compare this to what we wanted). We stop when \(0\le r\lt b\text{.}\) We repeatedly add \(b\) to negative numbers until \(0\le r\lt b\) is true. Since a negative number plus \(b\) is always less than \(b\) and we check the value of \(r\) after every addition, it is sufficient to check whether \(0\le r\text{.}\)
We illustrate the process of dividing a negative number by dividing \(-33\) by \(9\text{.}\) We repeatedly add \(9\) until we get a number from \(0\) to \(9-1=8\text{.}\) That number is the remainder. The negative of the number of times we add \(9\) is the quotient.
For the given values of \(a\) and \(b\text{,}\) determine the quotient \(q\) and remainder \(r\) of the division of \(a\) by \(b\text{,}\) and write the equality \(a=(q \cdot b) + r\text{.}\)
Using Algorithm 3.6 or Algorithm 3.14, we can compute the quotient and remainder of the division of any integer \(a\) by any natural number \(b\text{.}\) For \(a=0\) and any natural number \(b\) we have \(a=(q\cdot b)+r\) and \(0\le r\lt b\) when \(q=0\) and \(r=0\text{.}\)
Thus for all integers \(a\) and all natural numbers \(b\) we can find integers \(q\) and \(r\) such that \(a=(q\cdot b)+r\) and \(0\le r\lt b\text{.}\) We call the combination of the two algorithms the division algorithm.
Let \(a\) be an integer and \(b\) be a natural number, and let \(q\) and \(r\) be the unique integers such that \(0 \leq r \lt b\) and \(a=(q\cdot b)+r\text{.}\)
We call \(q\) the quotient of the division of \(a\) by \(b\) and denote it by \(a\fdiv b\text{.}\)
Example3.22.Previous results written with \(\fdiv\) and \(\fmod\).
In Example 3.7 we have seen that when dividing \(a=4\) by \(b=7\) the quotient is \(0\) and the remainder is \(4\text{.}\) Thus \(4=0\cdot 7+4\text{.}\) We write:
In Example 3.9 we have seen that when dividing \(a=30\) by \(b=8\) the quotient is \(q=3\) and the remainder is \(r=6\text{.}\) Thus \(30=3\cdot 8+6\text{.}\) We write:
In Example 3.9 we have seen that when dividing \(a=-20\) by \(b=7\) the quotient is \(-3\) and the remainder is \(1\text{.}\) Thus \(-20=(-3)\cdot 7+1\text{.}\) We write: