authored by Premmi and Beguène
Previous Topic : Well-Ordering Principle
Division Algorithm
The Division Algorithm establishes a relationship between two integers by asserting that an integer a can be divided by a positive integer b in such a way that the remainder is lesser than b. The usefulness of the Division Algorithm lies in its ability to allow us to prove assertions about all the integers by considering only a finite number of cases.
Intuition
Consider integers of the form 3q. These integers are shown in red on the number line below. We can see that these multiples of 3 are evenly spaced on the number line i.e., there are exactly two integers between each consecutive pair of multiples of 3.
As shown below, by adding 0, 1 \text{ or } 2 to each of these multiples of 3 we can cover every integer on the number line.
We can see from the number line shown above that from each integer on the number line there is only one multiple of 3 we can get by subtracting 0, 1 \text{ or } 2. Expressed in symbols, from each integer a we can subtract exactly one possible integer r, \text{ where } 0 \leq r \leq 2, to get only one possible multiple of 3. That is,
a - r = 3q
Rearranging this equation, we get
a = 3q + r
That is, there is only one possible ordered pair of integers (q, r) such that 0 \leq r \leq 2 \text{ and }a = 3q + r.
For every integer a, there is exactly one pair of integers (q, r) such that 0 \leq r \leq 2 \text{ and }a = 3q + r.
This is a very important idea in number theory which will help us prove many facts about integers.
The exact statement of this idea is the theorem below.
Theorem
The Division Algorithm states that for any integer a and a positive integer b there exists exactly one pair of integers q \text{ and } r such that
a = qb + r
where 0 \leq r < b.
The integers q \text{ and } r are called, respectively, the quotient and remainder in the division of a by b. We call a, the dividend and b, the divisor.
The Division Algorithm is also sometimes called the Division Theorem.
We can also think of r as the smallest integer we can subtract from a to get a multiple of b.
Proof
In order to prove this theorem we will show that
- there exists a nonnegative integer r such that r = a - qb \text{ and } 0 \leq r < b
- q \text{ and } r are unique i.e., there exists exactly one pair of integers (q, r) such that 0 \leq r < b \text{ and }a = qb + r
Let us first prove the existence of a nonnegative integer r such that r = a - qb \text{ and } 0 \leq r < b.
We will first prove that the nonnegative integer r = a - qb exists by constructing a set of non-negative integers of the form a - xb, where x is an integer and proving that this set is nonempty. Then from the Well-Ordering Principle we know that such a nonempty set of nonnegative integers will have a least element or equivalently, a smallest integer. We will next prove that this smallest integer is r and it is less than b i.e., 0 \leq r < b..
We begin by proving that the set
S = \{a-xb \,|\, x \text{ is an integer and } a-xb \geq 0\}is nonempty.
In order to prove that S is nonempty it suffices to find just one value of x such that a - xb is nonnegative.
Since b \geq 1, it follows that |a| b \geq |a|.
Therefore,
a - (-|a|b) = a + |a|b \geq a + |a| \geq 0
Hence, we have shown that for x = -|a|, a - xb \in S. Since S is a nonempty set of nonnegative integers, by the well-ordering principle the set S contains a least element i.e., a smallest integer. Let us call this integer r.
Since r \in S, by definition of S there exists an integer q such that
r = a - qb
where 0 \leq r.
We will now prove that r < b.
If this were not the case then, r \geq b and
a -qb \geq b
Adding -b to both sides of the equation, we get
a - qb -b \geq 0
Simplifying the above equation, we get
a - (q+1)b \geq 0
The integer a - (q+1)b has the right form to belong to S. But,
a - (q+1)b = a - qb -b = r - b < r
which contradicts our choice of r as the smallest member of S.
Since our assumption that r \geq b leads to a contradiction, it must be the case that r < b.
So far we have proved the existence of a nonnegative integer r such that r = a - qb \text{ and } 0 \leq r < b.
We will next prove that there exists exactly one pair of integers (q, r) such that 0 \leq r < b \text{ and }a = qb + r.
Suppose that integer a has two representations in the desired form, namely,
a = qb + r = q'b + r'
where 0 \leq r < b and 0 \leq r' < b.
Rearranging the terms of the equation,
qb + r = q'b + r'
we get,
r' - r = b(q-q')
Since the absolute value of a product is equal to the product of the absolute values,
|r' - r| = b|q-q'|
Multiplying the equation 0 \leq r < b with -1, we get
0 \geq -r > -b \implies -b < -r \leq 0
Adding the two equations,
\begin{equation*}
\begin{split}
0 & \leq r' < b \,\text{ and }\\
-b & < -r \leq 0 \\
\end{split}
\end{equation*} we get,
-b < r'-r < b
Therefore,
|r'-r| < b
Since,
\begin{equation*}
\begin{split}
|r' - r| &= b|q-q'| \, \text{ and }\\
|r'-r| &< b \\
\end{split}
\end{equation*} we get,
b|q-q'| < b \implies |q-q'| < 1
Therefore,
0 \leq |q-q'| < 1
Since |q-q'| is a nonnegative integer, the only possibility is that |q-q'| = 0 and hence, q = q' which in turn results in r = r'. This concludes our proof.
Loosening the restriction on b
Since a = qb + r, when b < 0 i.e., when b is negative we can get the same a by negating q. Therefore, we can obtain a more general version of the Division Algorithm by loosening the restriction that b must be positive and only requiring that it be nonzero i.e. b \neq 0.
Corollary
If a \text{ and } b are integers, with b \neq 0, then there exists exactly one pair of integers q \text{ and } r such that
a = qb + r
where 0 \leq r < |b|.
Proof
By the Division Algorithm proved above, if a \text{ and } b are integers, with b > 0, then there exists exactly one pair of integers q' \text{ and } r such that
a = q'b + r
where 0 \leq r < b.
Since b = |b|, it follows that a = q'b + r where 0 \leq r < |b|.
When b < 0, |b| = -b > 0.
Substituting b \text{ with } |b| in the above equation, we get
a = q'|b| + r
where 0 \leq r < |b|.
Let q'' = -q'. This implies that q' = -q''.
Substituting q' = -q'' \text{ and } |b| = -b in the above equation, we get
a = (-q'')(-b) + r
where 0 \leq r < |b|.
Therefore, when b < 0, a = q''b + r where 0 \leq r < |b|.
We will summarize what we have proved so far.
If a \text{ and } b are integers, with b > 0, then there exists exactly one pair of integers q' \text{ and } r such that
a = q'b + r
where 0 \leq r < |b|.
If a \text{ and } b are integers, with b < 0, then there exists exactly one pair of integers q'' \text{ and } r such that
a = q''b + r
where 0 \leq r < |b|.
Combining the above two statements we get the following statement.
If a \text{ and } b are integers, with b \neq 0, then there exists exactly one pair of integers q \text{ and } r such that
a = qb + r
where 0 \leq r < |b|.
This concludes our proof.
Applications of the Division Algorithm
The applications of the Division Algorithm is much more interesting than the algorithm itself as it helps us prove many assertions about integers.
We will see some numerical (American style 😏) as well as abstract (French style 😰) examples that illustrate the usefulness of the Division Algorithm.
Example 1
Suppose we are asked to find the greatest three-digit number that leaves a remainder of 6 when divided by 11. How would we go about finding such a number?
From the Division Algorithm we know that for an integer a and another integer b > 0 there exists unique integers q \text{ and } r such that a = qb + r \text{ and } 0 \leq r < b.
Here a \leq 999, b = 11 \text{ and } r = 6.
Therefore, a = 11q + 6 \leq 999.
Hence, q \leq \dfrac{993}{11} \implies q \leq 90\dfrac{3}{11}.
In order to get the largest possible a we need the largest possible q. Therefore, q = 90 and consequently, a = 11 \times 90 + 6 = 996.
Therefore the greatest three-digit number that leaves a remainder of 6 when divided by 11 is 996.
Next let us consider a more sophisticated example of an application of the Division Algorithm.
Example 2
Suppose we are asked to prove that 3n^2-1 (where n is an integer) can never be a perfect square. How would we go about proving this assertion?
Since the expression 3n^2-1 is a multiple of 3 from which 1 has been subtracted, from the Division Algorithm we know that we can express any integer as multiple of 3 plus some remainder ranging from 0 \text{ to } 2. We will square integers of this form and prove that they can never be of the form 3n^2-1.
From the Division Algorithm we know that when b = 3, the possible remainders are r = 0, r = 1 \text{ and } r = 2. When r = 0, the integer a has the form 3q, when r = 1, the integer a has the form 3q + 1 and when r = 2, the integer a has the form 3q + 2.
Hence, by the Division Algorithm, any integer is representable as one of the three forms, namely, 3q, 3q + 1 \text{ and } 3q+2. Therefore, by squaring each of these possible forms of integer a, we get all possible forms the square of an integer may assume.
- When a = 3q
a^2 = (3q)^2 = 9q^2 = 3 \cdot 3q^2 = 3k, where k = 3q^2 is an integer. - When a = 3q + 1
a^2 = (3q +1)^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1 = 3k + 1, where k = 3q^2 + 2q is an integer. - When a = 3q + 2
a^2 = (3q +2)^2 = 9q^2 + 12q + 4 = 3(3q^2 + 4q) + 3 + 1 = 3(3q^2 + 4q + 1) + 1= 3k + 1, where k = 3q^2 + 4q + 1 is an integer.
Hence, the square of any integer is either of the form 3k \text{ or } 3k + 1.
We have to prove that the square of an integer cannot be of the form 3n^2-1. Suppose the square of an integer is of this form. Then, if a^2 = 3k \implies 3n^2-1 = 3k\implies 3(n^2 - k) = 1 \implies n^2 - k = \dfrac{1}{3}. This is impossible since an integer subtracted from another integer cannot result in a fraction.
Similarly, if a^2 = 3k + 1 \implies 3n^2-1 = 3k + 1 \implies 3(n^2-k) = 2 \implies n^2 - k = \dfrac{2}{3}, which is impossible.
Therefore, our assumption that 3n^2-1 is a perfect square is incorrect and hence we have proved that 3n^2-1 can never be a perfect square.
Next Topic : The Greatest Common Divisor