Added to Favorites

Related Searches

Definitions

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 — although the division algorithm can be used to find the greatest common divisor of two integers.## Statement of theorem

Specifically, the division algorithm states that given two integers a and d, with d ≠ 0 ## Examples

## Proof

The proof consists of two parts — first, the proof of the existence of q and r, and second, the proof of the uniqueness of q and r.
### Existence

Consider the set### Uniqueness

Suppose there exists q, q' , r, r' with 0 ≤ r, r' < |d| such that a = dq + r and a = dq' + r' . Without loss of generality we may assume that q ≤ q' .
## Generalizations

There is nothing particularly 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

It should be noted that the term "division algorithm" in the study of algebra is commonly applied to the more general variant of this theorem, shown to hold in integral domains which are principal ideal domains.

There exist 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 called the quotient
- r is called the remainder
- d is called the divisor
- a is called the dividend

- If a = 7 and d = 3, then q = 2 and r = 1, since 7 = (2)(3) + 1.
- If a = 7 and d = −3, then q = −2 and r = 1, since 7 = (−2)(−3) + 1.
- If a = −7 and d = 3, then q = −3 and r = 2, since −7 = (−3)(3) + 2.
- If a = −7 and d = −3, then q = 3 and r = 2, since −7 = (3)(−3) + 2.

- $S\; =\; left\{a\; -\; nd\; :\; n\; in\; mathbb\{Z\}right\}.$

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 (−d)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 implies a-qd ≥ d. This implies that a-qd-d ≥0, further implying that a-(q+1)d ≥ 0. Therefore, a-(q+1)d is in S and, since a-(q+1)d=r-d with d>0 we know a-(q+1)d<r, contradicting the assumption that r was the least nonnegative element of S.
- If d<0 then r ≥ -d implying that a-qd ≥ -d. This implies that a-qd+d ≥0, further implying that a-(q-1)d ≥ 0. Therefore, a-(q-1)d is in S and, since a-(q-1)d=r+d with d<0 we know a-(q-1)d<r, contradicting the assumption that r was the least nonnegative element of S.

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.

Subtracting the two equations yields: d(q' - q) = (r - r' ).

If d > 0 then r' ≤ r and r < d ≤ d+r' , and so (r-r' ) < d. Similarly, if d < 0 then r ≤ r' and r' < -d ≤ -d+r, and so -(r- r' ) < -d. Combining these yields |r- r' | < |d|.

The original equation implies that |d| divides |r- r' |; therefore either |d| ≤ |r- 'r' | or |r- r' |=0. Because we just established that |r-r' | < |d|, by trichotomy we may conclude that the first possibility cannot hold. Thus, r=r' .

Substituting this into the original two equations quickly yields dq = dq' and, since we assumed d is not 0, it must be the case that q = q' proving uniqueness.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday September 20, 2008 at 02:18:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday September 20, 2008 at 02:18:03 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.