Division algorithm

﻿
Division algorithm

In mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be specified precisely by a theorem stating that these exist uniquely with given properties. An integer division algorithm is any effective method for producing such quotient and remainder. Using the decimal notation of integers (or any other positional notation), long division provides a fairly efficient division algorithm, and other algorithms exist as well. The integer division algorithm is an important ingredient for other algorithms, such as the Euclidean algorithm for finding the greatest common divisor of two integers.

The term "division algorithm" is also used in abstract algebra for any effective procedure in a Euclidean domain that makes explicit their defining property, by producing for a given dividend and nonzero divisor a quotient and a remainder such that the remainder is smaller than the divisor in the appropriate sense.

Statement of theorem

Specifically, the division algorithm states that given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b.

The integer

• q is called the quotient
• r is called the remainder
• b is called the divisor
• a is called the dividend

Examples

• If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 2 × 3 + 1.
• If a = 7 and b = − 3, then q = − 2 and r = 1, since 7 = − 2 × (− 3) + 1.
• If a = − 7 and b = 3, then q = − 3 and r = 2, since − 7 = − 3 × 3 + 2.
• If a = − 7 and b = − 3, then q = 3 and r = 2, since − 7 = 3 × (− 3) + 2.

A 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 $S = \left\{a - nb : n \in \mathbb{Z}\right\}.$

We claim that S contains at least one nonnegative integer. There are two cases to consider.

• If a is nonnegative, then choose n = 0.
• If a is negative, then choose n = ab.

In both cases, a - nb is nonnegative, and thus S always contains at least one nonnegative integer. This means we can apply the well-ordering principle, and deduce that S contains a least nonnegative integer r. By definition, r = a - nb for some n. Let q be this n. Then, by rearranging the equation, a = qb + r.

It only remains to show that 0 ≤ r < |b|. The first inequality holds because of the choice of r as a nonnegative integer. To show the last (strict) inequality, suppose that r ≥ |b|. Since b ≠ 0, r > 0, and again b > 0 or b < 0.

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

Uniqueness

Suppose there exists q, q' , r, r' with 0 ≤ r, r' < |b| such that a = bq + r and a = bq' + r' . Without loss of generality we may assume that qq' .

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

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

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

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

An alternative proof

First note that for any integers a, b, q, r, the relation a = bq + r is equivalent both to a = −b×−q + r and to −1 − a = b(−1 − q) + b − 1 − r, so that the pair (q,r) is a solution for the division of a by b if and only if (−q,r) is a solution for the division of a by b, and also if and only if (−1 − q,b − 1 − r) is a solution for the division of −1 − a by b. It will therefore suffice to prove existence and uniqueness of these solutions assuming b > 0 and a ≥ 0: existence and uniqueness in the other cases will follow from it by these equivalences. We assume these inequalities henceforth, and observe that they imply that q ≥ 0 for any possible solution (as q ≤ −1 together with the required r < b would imply bq + r < 0).

Informally, one finds r by repeatedly subtracting b from a until finding a value less than b, and shows that it is the unique possibility for the remainder (the uniqueness of the quotient then follows). Formally this part of the proof is by induction, and establishes existence and uniqueness at the same time.

An inductive proof for the case a ≥ 0 and b > 0

For fixed divisor b one proceeds by induction on the size of the dividend a. All cases with a < b are taken together as the starting case for the induction (they include at the very least the case a = 0). In this case the pair q = 0 and r = a proves the existence part. For the uniqueness part consider q first: one cannot have a = bq + r with q > 0 and r ≥ 0 since a < b, so q = 0 is the only possible value, but then necessarily r = abq = a, so r is unique as well.

For the inductive step, suppose ab, and suppose the statement holds for all dividends less than a. In particular it holds for ab, so there exist unique values q′ and r′ such that ab = qb + r and r′ < b. Now in order to have a = bq + r with r < b one cannot have q = 0, so necessarily q − 1 ≥ 0. The equation a = bq + r then is equivalent to

ab = bq + rb = (q − 1)b + r

and by the statement for ab this holds if and only if q − 1 = q and r = r. So the pair given by q = q′ + 1 and r = r is the unique solution in this case, completing the proof.

Effectiveness

A proof of the theorem is not an algorithm to compute a quotient and a remainder. However, a recursive algorithm can be immediately obtained from the second proof. For the case of nonnegative dividend and divisor, it states that if a < b then q = 0 and r = a, and otherwise applies the algorithm recursively to ab and b, and adds one to the quotient found for that case, keeping the same remainder. The results for one or more negative arguments are deduced from those for positive arguments as indicated in the proof. This is not a very efficient method, as it requires as many steps as the size of the quotient. This is related to the fact that it only uses the basic arithmetic operations and comparisons of the integers, as opposed to any particular representation of them such as decimal notation; this gives no access even to coarse estimates of the size of the operands, such as their number of digits, although such information will usually be available when concretely giving a and b. In terms of decimal notation, long division provides a much more efficient division algorithm.

By contrast, alternative algorithms that could be formulated in terms of operations on rational numbers or even on real numbers do not constitute useful division algorithms, since realizing such operations effectively requires being able to perform operations of integer arithmetic, and notably the integer division algorithm (to find the integral part of a rational number for instance).

Wikimedia Foundation. 2010.

Look at other dictionaries:

• division algorithm — Math. 1. the theorem that an integer can be written as the sum of the product of two integers, one a given positive integer, added to a positive integer smaller than the given positive integer. Cf. Euclidean algorithm. 2. any systematic process… …   Universalium

• division algorithm — Math. 1. the theorem that an integer can be written as the sum of the product of two integers, one a given positive integer, added to a positive integer smaller than the given positive integer. Cf. Euclidean algorithm. 2. any systematic process… …   Useful english dictionary

• Multivariate division algorithm — In mathematics, polynomials in more than one variable do not form a Euclidean domain, so it is not possible to construct a true division algorithm; but an approximate multivariate division algorithm can be constructed. Given a polynomial g,… …   Wikipedia

• Division (digital) — Several algorithms exist to perform division in digital designs. These algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow… …   Wikipedia

• Division (mathematics) — Divided redirects here. For other uses, see Divided (disambiguation). For the digital implementation of mathematical division, see Division (digital). In mathematics, especially in elementary arithmetic, division (÷ …   Wikipedia

• Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

• Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

• Division polynomials — In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves over Finite fields. They play a central role in the study of counting points on elliptic curves in Schoof s algorithm. Contents 1 Definition …   Wikipedia

• Division by two — In mathematics, division by two or halving has also been called mediation or dimidiation. The treatment of this as a different operation from multiplication and division by other numbers goes back to the ancient Egyptians, whose multiplication …   Wikipedia

• algorithm — algorithmic, adj. /al geuh ridh euhm/, n. a set of rules for solving a problem in a finite number of steps, as for finding the greatest common divisor. [1890 95; var. of ALGORISM, by assoc. with Gk arithmós number. See ARITHMETIC] * * * Procedure …   Universalium