Subsection Division 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{.}\)
We typically use the variable \(q\) for the quotient and the variable \(r\) for the remainder. We have
\begin{equation*}
r=a\underbrace{-b - b-\ldots-b}_{\mbox{\(q\) times} }=a-(\underbrace{b + b+\ldots+b}_{\mbox{\(q\) times} })=a-(q\cdot b)\text{.}
\end{equation*}
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.
Algorithm 3.6. Division for positive numbers.
- Input:
a natural number \(a\) and a natural number \(b\)
- Output:
Two integers \(q\) and \(r\) such that \(a=(q\cdot b)+r\) and \(0 \leq r\lt b\)
if \(a\lt b\) then return \(0,a\)
let \(q:=0\)
let \(r:=a\)
repeat
let \(q:=q+1\)
let \(r:=r-b\)
until \(r\lt b\)
return \(q,r\)
We first consider an example in which the algorithm terminates before we enter the repeat_until loop.
Example 3.7. Dividing \(4\) by \(7\) with Algorithm 3.6.
We find the output values of
Algorithm 3.6 for the input values
\(a=4\) and
\(b=7\text{.}\)
Input: \(a=4\) and \(b=7\)
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.
Output: \(0\text{,}\)\(4\)
Thus the quotient of the division of \(4\) by \(7\) is \(0\) and the remainder is \(4\text{.}\)
With the division algorithm we find a quotient and remainder. In this example we go through the repeat_until loop several times.
Example 3.8. Dividing \(30\) by \(8\) with Algorithm 3.6.
We find the output values of the
Algorithm 3.6 for the input values
\(a=30\) and
\(b=8\text{.}\)
Input: \(a=30\) and \(b=8\)
1. As
\(a=30\) and
\(b=8\) the statement
\(a \lt b\) is false. So we continue with
step 2.
5. As
\(r=22\) and
\(q=1\) the statement
\(r \lt q\) is false. So we continue with
step 4
5. As
\(r=14\) and
\(q=8\) the statement
\(r \lt q\) is false. So we continue with
step 4
As
\(r=6\) and
\(q=8\) the statement
\(r\lt q\) is true. So we continue with
step 6.
We return the quotient \(q=3\) and the remainder \(r=6\)
Output: \(3\text{,}\) \(6\)
Thus the quotient of the division of \(30\) by \(8\) is \(3\) and the remainder is \(6\text{.}\)
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.
Example 3.9. Dividing \(30\) by \(8\) with Algorithm 3.6 shorter.
We find the output values of
Algorithm 3.6 for the input values
\(a=30\) and
\(b=8\text{.}\)
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.
| Input |
\(30\) |
\(8\) |
\(\) |
\(\) |
| 1.,2.,3. |
\(30\) |
\(8\) |
\(0\) |
\(30\) |
| 4.,5. |
\(30\) |
\(8\) |
\(0+1=1\) |
\(30-8=22\) |
| 4.,5. |
\(30\) |
\(8\) |
\(1+1=2\) |
\(22-8=14\) |
| 4.,5. |
\(30\) |
\(8\) |
\(1+1=3\) |
\(14-8=6\) |
| Output |
\(\) |
\(\) |
\(3\) |
\(6\) |
So the output is \(q=3\) and \(r=6\)
In
Example 3.10 you can observe how the values of the variables change as you click your way through the steps of the division algorithm.
Example 3.10. Division algorithm positive interactive.
Checkpoint 3.11. Find quotient and remainder with division algorithm.
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.
Checkpoint 3.12. Another variant of the division algorithm.
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{.}\)
Subsection Division Algorithm for Negative Integers
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
\begin{equation*}
r=a\underbrace{+b + b+\ldots+b}_{\mbox{\(s\) times} }=a+(b\cdot s)\text{.}
\end{equation*}
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{.}\)
Example 3.13. Dividing \(-33\) by \(9\).
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.
\begin{align*}
-33 + 9 \amp = -24\\
-24 + 9 \amp = -15\\
-15 + 9 7\amp = -6\\
-6 + 9 \amp = 3
\end{align*}
As \(0\le 3\lt 9\) we are done. The remainder is \(3\text{.}\) We have added \(9\) four times, so the quotient is \(-4\text{.}\) We have
\begin{equation*}
-33 + 9\cdot 4 + 3\mbox{ or } -33=-(9\cdot 4) + 3 \mbox{ or } -33=9\cdot(-4)+3\text{.}
\end{equation*}
We now formalize this procedure in an algorithm.
Algorithm 3.14. Division for negative integers.
- Input:
A negative integer \(a\) and a natural number \(b\)
- Output:
Two integers \(q\) and \(r\) such that \(a=(q\cdot b)+r\) and \(0 \leq r\lt b\)
let \(q:=0\)
let \(r:=a\)
repeat
let \(q:=q-1\)
let \(r:=r+b\)
until \(r\ge 0\)
return \(q,r\)
Example 3.15. \(-20\fdiv 7\) and \(-20\fmod 7\) with Algorithm 3.14.
We find the output values of the Division Algorithm (
Algorithm 3.14) for the input values
\(a=-20\) and
\(b=7\text{.}\)
Input: \(a=-20\) and \(b=7\)
3.b.
let \(r:=-20+7=-13\)
4. As
\(r=-20\) the statement
\(r\ge 0\) is false. So we continue with
step 3.
4. As
\(r=-6\) the statement
\(r\ge 0\) is false. So we continue with
step 3.
4. As
\(r=1\) the statement
\(r\ge 0\) is false. So we continue with
step 5.
5. We return the quotient
\(q=-3\) and the remainder
\(r=1\)
Output: \(-3\text{,}\) \(1\)
Thus the quotient or the division of \(-20\) by \(7\) is \(-3\) and the remainder is \(1\text{.}\)
In
Example 3.16 you can observe how the values of the variables change as you click your way thought the steps of the division algorithm.
Example 3.16. Division algorithm negative interactive.
Checkpoint 3.17. Find quotient and remainder with division algorithm.
We give some more examples.
Example 3.18. Previous result written as \(a=(q\cdot b)+r\).
In
Example 3.7 we have seen that when dividing
\(a=4\) by
\(b=7\) the quotient is
\(q=0\) and the remainder is
\(r=4\text{.}\) Thus we have:
\begin{equation*}
4=(7 \cdot 0) + 4
\end{equation*}
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 we have:
\begin{equation*}
30=(3 \cdot 8) + 6
\end{equation*}
In
Example 3.9 we have seen that when dividing
\(a=-20\) by
\(b=7\) the quotient is
\(q=-3\) and the remainder is
\(r=1\text{.}\) Thus we have:
\begin{equation*}
-20=(7 \cdot (-3)) + 1
\end{equation*}
Problem 3.19. Write as \(a=(q\cdot b)+r\).
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{.}\)
\(a=7\) and \(b=3\)
\(a=7\) and \(b=8\)
\(a=20\) and \(b=4\)
\(a=-13\) and \(b=3\)
Solution.
The answers are provided here, but details for the solution are omitted.
For \(a=7\) and \(b=3\text{,}\) we have \(q=2\) and \(r=1\text{,}\) and write \(7=(3\cdot 2)+1\text{.}\)
For \(a=7\) and \(b=8\text{,}\) we have \(q=0\) and \(r=7\text{,}\) and write \(7=(8\cdot 0)+7\text{.}\)
For \(a=20\) and \(b=4\text{,}\) we have \(q=5\) and \(r=0\text{,}\) and write \(20=(4\cdot 5)+0\text{.}\)
For \(a=-13\) and \(b=3\text{,}\) we have \(q=-5\) and \(r=2\text{,}\) and write \(-13=(3\cdot (-5)) +2\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.
Subsection \(\fdiv\) and \(\fmod\)
Theorem 3.20.
Let \(a\) be an integer and \(b\) be a natural number. Then, there exist unique integers \(q\) and \(r\) with \(0 \leq r \lt b\) such that
\begin{equation*}
a=(q\cdot b)+ r\text{.}
\end{equation*}
Next we introduce notation for the the quotient and remainder of the division of an integer by a natural number.
Definition 3.21.
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{.}\)
We call \(r\) the remainder of the division of \(a\) by \(b\) and denote it by \(a\fmod b\text{.}\)
We rewrite the quotient and remainder from some of the previous examples with \(\fdiv\) and \(\fmod\text{.}\)
Example 3.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:
\(4 \fdiv 7 = 0\) and \(4\fmod 7=4\)
-
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:
\(30 \fdiv 8 = 3\) and \(30\fmod 8 = 6\)
-
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:
\(-20 \fdiv 7 = -3\) and \(-20\fmod 7=1\)
In the
Checkpoint 3.23 write the quotient and remainder with the new operations
\(\fdiv\) and
\(\fmod\text{.}\)
Checkpoint 3.23. \(a \fdiv b\) and \(a \fmod b\) from \(a=q\cdot b+r\).
When we are given the quotient and remainder from the division of an integer \(a\) by a natural number \(b\text{,}\) we can recover \(a\text{.}\)
Problem 3.24. \(a\) from \(a \fdiv b\) and \(a \fmod b\).
Assume \(a\) is the integer such that
\begin{equation*}
a \fdiv 42 = 10
\end{equation*}
and
\begin{equation*}
a \fmod 42 = 7.
\end{equation*}
What is \(a\) ?
Solution.
By
Theorem 3.20 we know that
\(a\) can be written in the form
\begin{equation*}
a=(q\cdot 42)+ r.
\end{equation*}
\begin{equation*}
q = a \fdiv 42
\end{equation*}
and
\begin{equation*}
r=a\fmod 42.
\end{equation*}
Replacing \(q\) and \(r\) by these expressions we get
\begin{equation*}
a=((a\fdiv 42)\cdot 42)+ (a\fmod 42).
\end{equation*}
We are given exactly these two values, in particular
\begin{equation*}
a \fdiv 42 = 7
\end{equation*}
and
\begin{equation*}
a \fmod 42 = 10.
\end{equation*}
Thus we can replace \(a \fdiv 42\) by \(10\) and \(a \fmod 42\) by \(7\) in the equation above and get
\begin{equation*}
a = (10\cdot 42)+7.
\end{equation*}
Evaluating the expression we get
\begin{equation*}
a = (10\cdot 42)+7 = 420+7=427.
\end{equation*}
In
Checkpoint 3.25 use conduct the computation from the example above to find the integer
\(a\) when given
\(a \fdiv b\) and
\(a \fmod b\text{.}\)
Checkpoint 3.25. Find \(a\) from \(a \fdiv b\) and \(a \fmod b\).
