Division algorithm
Encyclopedia
In mathematics
, and more particularly in arithmetic
, the usual process of division
of integer
s 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.
integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value
of b.
The integer
We claim that S contains at least one nonnegative integer. There are two cases to consider.
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.
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.
Subtracting the two equations yields: b(q' - q) = (r - r' ).
If b > 0 then r' ≤ r and r < b ≤ b + r' , and so (r - r' ) < b. Similarly, if b < 0 then r ≤ r' 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.
is a solution for the division of by , and also if and only if is a solution for the division of by . It will therefore suffice to prove existence and uniqueness of these solutions assuming and : 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 for any possible solution (as together with the required would imply ).
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.
on the size of the dividend a. All cases with are taken together as the starting case for the induction (they include at the very least the case ). In this case the pair and proves the existence part. For the uniqueness part consider q first: one cannot have with and since , so is the only possible value, but then necessarily , so r is unique as well.
For the inductive step, suppose , and suppose the statement holds for all dividends less than a. In particular it holds for , so there exist unique values q′ and r′ such that and . Now in order to have with one cannot have , so necessarily . The equation then is equivalent to
and by the statement for this holds if and only if and . So the pair given by and is the unique solution in this case, completing the proof.
algorithm can be immediately obtained from the second proof. For the case of nonnegative dividend and divisor, it states that if then and , and otherwise applies the algorithm recursively to 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 and . 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 number
s or even on real number
s 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).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, and more particularly in arithmetic
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
, the usual process of division
Division (mathematics)
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s producing a quotient
Quotient
In mathematics, a quotient is the result of division. For example, when dividing 6 by 3, the quotient is 2, while 6 is called the dividend, and 3 the divisor. The quotient further is expressed as the number of times the divisor divides into the dividend e.g. The quotient of 6 and 2 is also 3.A...
and a remainder
Remainder
In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....
can be specified precisely by a theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
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
Positional notation
Positional notation or place-value notation is a method of representing or encoding numbers. Positional notation is distinguished from other notations for its use of the same symbol for the different orders of magnitude...
), long division
Long division
In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...
provides a fairly efficient division algorithm, and other algorithms
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 division include restoring, non-performing restoring,...
exist as well. The integer division algorithm is an important ingredient for other algorithms, such as the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
for finding the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
of two integers.
The term "division algorithm" is also used in abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
for any effective procedure in a Euclidean domain
Euclidean domain
In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm...
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 uniqueUniqueness quantification
In mathematics and logic, the phrase "there is one and only one" is used to indicate that exactly one object with a certain property exists. In mathematical logic, this sort of quantification is known as uniqueness quantification or unique existential quantification.Uniqueness quantification is...
integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value
Absolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
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 setWe 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
Well-ordering principle
The "well-ordering principle" is a property of ordered sets. A set X is well ordered if every subset of X has a least element. An example of a well ordered set is the set of natural numbers. An example of set that is not well ordered is the set of integers...
, 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 r ≥ b implies 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.
- 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 q ≤ q' .Subtracting the two equations yields: b(q' - q) = (r - r' ).
If b > 0 then r' ≤ r and r < b ≤ b + r' , and so (r - r' ) < b. Similarly, if b < 0 then r ≤ r' 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 , , , , the relation is equivalent both to and to , so that the pair is a solution for the division of by if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
is a solution for the division of by , and also if and only if is a solution for the division of by . It will therefore suffice to prove existence and uniqueness of these solutions assuming and : 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 for any possible solution (as together with the required would imply ).
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 and
For fixed divisor b one proceeds by inductionMathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
on the size of the dividend a. All cases with are taken together as the starting case for the induction (they include at the very least the case ). In this case the pair and proves the existence part. For the uniqueness part consider q first: one cannot have with and since , so is the only possible value, but then necessarily , so r is unique as well.
For the inductive step, suppose , and suppose the statement holds for all dividends less than a. In particular it holds for , so there exist unique values q′ and r′ such that and . Now in order to have with one cannot have , so necessarily . The equation then is equivalent to
and by the statement for this holds if and only if and . So the pair given by and 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 recursiveRecursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
algorithm can be immediately obtained from the second proof. For the case of nonnegative dividend and divisor, it states that if then and , and otherwise applies the algorithm recursively to 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 and . In terms of decimal notation, long division
Long division
In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...
provides a much more efficient division algorithm.
By contrast, alternative algorithms that could be formulated in terms of operations on rational number
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s or even on real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s 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).