Division algorithm
|
|
The division algorithm is a theorem in mathematics which precisely expresses the outcome of the usual process of division of integers. The name is something of a misnomer, as it is a theorem, not an algorithm, i.e. a well-defined procedure for achieving a specific task.
| Contents |
Statement of theorem
Specifically, the division algorithm states that given two integers a and d, with d ≠ 0, there exists unique integers q and r such that a = qd + r and 0 ≤ r < |d|, where |d| denotes the absolute value of d. The integer q is the quotient, r is the remainder, d is the divisor, and a is the dividend.
Examples
- If a = 7 and d = 3, then q = 2 and r = 1.
- If a = 7 and d = −3, then q = −2 and r = 1.
- If a = −7 and d = 3, then q = −3 and r = 2.
- If a = −7 and d = −3, then q = 3 and r = 2.
Proof
The proof consists of two parts — first, the proof of the existence of q and r, and secondly, the proof of the uniqueness of q and r.
Existence
Consider the set
- <math>S = \left\{a - nd : n \in \mathbb{Z}\right\}<math>
We claim that S contains at least one nonnegative integer. There are two cases to consider.
- If d < 0, then −d > 0, and by the Archimedean property, there is a nonnegative integer n such that (−b)n ≥ −a, i.e. a − dn ≥ 0.
- If d > 0, then again by the Archimedean property, there is a nonnegative integer n such that dn ≥ −a, i.e. a − d(−n) = a + dn ≥ 0.
In either case, we have shown that S contains a nonnegative integer. This means we can apply the well-ordering principle, and deduce that S contains a least nonnegative integer r. If we now let q = (a − r)/d, then q and r are integers and a = qd + r.
It only remains to show that 0 ≤ r < |d|. The first inequality holds because of the choice of r as a nonnegative integer. To show the last (strict) inequality, suppose that r = |d|. Since d ≠ 0, r > 0, and again d > 0 or d < 0.
- If d > 0, then r = d. Let q' = q + 1; then q' is an integer and q'd = (q + 1)d = qd + d = qd + r = a, i.e. a − q'd = 0.
- If d < 0, then r = −d. Let q' = q − 1; then q' is an integer and q'd = (q − 1)d = qd − d = qd + r = a, i.e. a − q'd = 0.
In either case, we have shown that r > 0 was not really the least nonnegative integer in S, after all. This is a contradiction, and so we must have r < |d|. This completes the proof of the existence of q and r.
Uniqueness
Since r = a − qd, it is enough to prove the uniqueness of q. So, suppose there exist integers q and q' satisfying the result of the theorem. Then we must have 0 ≤ a − qd < |d| and 0 ≤ a − q'd < |d|. Note that
- <math>(q' - q)d = (a - qd) - (a - q'd) \leq (a - qd) < |d|<math>
- <math>(q' - q)d = (a - qd) - (a - q'd) \geq 0 - (a - q'd) = -(a - q'd) > -|d|<math>
Together, these two inequalities show that (q' − q)d is an integer whose absolute value is strictly less than |d|. Since |d| > 0, division gives
- <math>-1 < \pm (q' - q) < 1<math>
Since q' − q is an integer, we must have q' − q = 0, i.e. q = q'. This completes the proof of the uniqueness of q and r.
Generalisations
There is nothing particular special about the set of remainders {0, 1, ..., |d| − 1}. We could use any set of |d| integers, such that every integer is congruent to one of the integers in the set. This particular set of remainders is very convenient, but it is not the only choice. See also coset and equivalence relation.
External links
- Informal discussion of the division algorithm and well-ordering principle (http://www.math.hawaii.edu/~lee/courses/Division.pdf)de:division mit Rest