In arithmetic, Euclidean division or division with remainder is the process of division of two integers, which produces a quotient and a remainder smaller than the divisor. Its main property is that the quotient and remainder exist and are unique, under some conditions. Because of this uniqueness, Euclidean division is often considered without referring to any method of computation, and without explicitly computing the quotient and the remainder. The methods of computation are called integer division algorithms, the best known being long division.
Euclidean division, and algorithms to compute it, are fundamental for many questions concerning integers, such as the Euclidean algorithm for finding the greatest common divisor of two integers, and modular arithmetic, for which only remainders are considered. The operation consisting of computing only the remainder is called the modulo operation.
Statement of the theorem
Given two integers a and b, with b ≠ 0, there exist unique integers q and r such that
- a = bq + r
- 0 ≤ r < |b|,
The four integers that appear in this theorem have been given names: a is called the dividend, b is called the divisor, q is called the quotient and r is called the remainder.
The computation of the quotient and the remainder from the dividend and the divisor is called division or, in case of ambiguity, Euclidean division. The theorem is frequently referred to as the division algorithm, although it is a theorem and not an algorithm, because its proof as given below also provides a simple division algorithm for computing q and r.
Division is not defined in the case where b = 0; see division by zero.
This section does not cite any sources. (September 2016) (Learn how and when to remove this template message)
Although "Euclidean division" is named after Euclid, it seems that he did not know the existence and uniqueness theorem, and that the only computation method that he knew was the division by repeated subtraction.
Before the discovery of Hindu–Arabic numeral system, which was introduced in Europe during the 13th century by Fibonacci, division was extremely difficult, and only the best mathematicians were able to do it. In fact, the long division algorithm requires this notation.
The term "Euclidean division" was introduced during the 20th century as a shorthand for "division of Euclidean rings". It has been rapidly adopted by mathematicians for distinguishing this division from the other kinds of division of numbers.
Suppose that a pie has 9 slices and they are to be divided evenly among 4 people. Using Euclidean division, 9 divided by 4 is 2 with remainder 1. In other words, each person receives 2 slices of pie, and there is 1 slice left over.
This can be confirmed using multiplication, the inverse of division: if each of the 4 people received 2 slices, then 4 × 2 = 8 slices were given out in all. Adding the 1 slice remaining, the result is 9 slices. In summary: 9 = 4 × 2 + 1.
In general, if the number of slices is denoted a and the number of people is b, one can divide the pie evenly among the people such that each person receives q slices (the quotient) and some number of slices r < b are left over (the remainder). Regardless, the equation a = bq + r holds.
If 9 slices were divided among 3 people instead of 4, each would receive 3 and no slices would be left over. In this case the remainder is zero, and it is said that 3 evenly divides 9, or that 3 divides 9.
Euclidean division can also be extended to negative integers using the same formula; for example −9 = 4 × (−3) + 3, so −9 divided by 4 is −3 with remainder 3.
- If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 3 × 2 + 1.
- If a = 7 and b = −3, then q = −2 and r = 1, since 7 = −3 × (−2) + 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.
The following proof of the division theorem relies on the fact that a decreasing sequence of nonnegative integers stops eventually. This proof is separated into two parts, one for existence and another for uniqueness of q and r. Other proofs use the well-ordering principle that asserts that a nonempty set of nonnegative integers has a smallest element. They may be simpler, but have the disadvantage of not providing directly an algorithm (see § Effectiveness).
Consider first the case b < 0. Setting b' = –b and q' = –q, the equation a = bq + r may be rewritten a = b'q' + r and the inequality 0 ≤ r < |b| may be rewritten 0 ≤ r < b′. This reduces the existence for the case b < 0 to that of the case b > 0.
Similarly, if a < 0 and b > 0, setting a' = –a, q' = –q – 1, and r' = b – r, the equation a = bq + r may be rewritten a' = bq' + r′, and the inequality 0 ≤ r < b may be rewritten 0 ≤ r' < b. Thus the proof of the existence is reduced to the case a ≥ 0 and b > 0 and we consider only this case in the remainder of the proof.
Let q1 = 0 and r1 = a. They are nonnegative numbers such that a = bq1 + r1. If r1 < b then we are done, so suppose r1 ≥ b. Then defining q2 = q1 + 1 and r2 = r1 – b, one has a = bq2 + r2 and 0 ≤ r2 < r1. As there are only r1 nonnegative integers less than r1, one may repeat this process at most r1 times, that is, there exist k ≤ r1, qk, and rk such that a = bqk + rk and 0 ≤ rk < b.
This proves the existence and also gives a simple division algorithm to compute the quotient and the remainder. However this algorithm is not efficient, since its number of steps is of the order of a/b.
The pair of integers r and q such that a = bq + r is unique, i.e. no other pair of integers satisfies the Euclidean division theorem. In other words, if we have another division of a by b, say a = bq' + r', with r' < |b|, then we have
- q' = q and r' = r.
To prove this statement, write first the hypotheses:
- 0 ≤ r < |b|
- 0 ≤ r' < |b|
- a = bq + r
- a = bq' + r'
Subtracting the two equations yields
- b(q – q′) = r – r′.
So b is a divisor of r – r′. As
- |r – r′| < |b|
by the above inequalities, one gets
- r – r′ = 0,
- b(q – q′) = 0.
As b ≠ 0, this proves the uniqueness.
Generally, an existence proof does not provide an algorithm to compute the existing object, but the above proof provides immediately an algorithm (see Division algorithm#Division by repeated subtraction). However 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 addition, subtraction and comparison of the integers, without involving multiplication, nor any particular representation of the integers, such as decimal notation.
In terms of decimal notation, long division provides a much more efficient division algorithm. Its generalization to binary notation allows use in a computer. However, for large inputs, algorithms that reduce division to multiplication, such as Newton–Raphson, are usually preferred, because they need a time which is proportional to the time of the multiplication needed to verify the result, independently of the multiplication algorithm which is used.
The Euclidean division admits a number of variants, some of which are listed below.
Other intervals for the remainder
In Euclidean division with q as divisor, the remainder is supposed to belong to the interval [0, q) of length |q|. Any other interval of the same length may be used. More precisely, given integers , , with , there exist unique integers and with such that .
Especially, if then . This division is called the centered division, and its remainder is called the centered remainder or least absolute remainder.
Given integers , and with and let be the modular multiplicative inverse of (that is and is a multiple of ). Then there exist unique integers and with such that . This result generalizes Hensel's odd division (1900).
The value is the N-residue defined in Montgomery reduction.
In Euclidean domains
- Given an element a and a non-zero element b in a Euclidean domain R equipped with a Euclidean function d (also known as a Euclidean valuation or degree function), there exist q and r in R such that a = bq + r and either r = 0 or d(r) < d(b).
Uniqueness of q and r is not required. It occurs only in exceptional cases, typically for univariate polynomials, and for integers, if the further condition r ≥ 0 is added.
Examples of Euclidean domains include fields, polynomial rings in one variable over a field, and the Gaussian integers. The Euclidean division of polynomials has been the object of specific developments. See Polynomial long division, Polynomial greatest common divisor#Euclidean division and Polynomial greatest common divisor#Pseudo-remainder sequences.
- Burton, David M. (2010). Elementary Number Theory. McGraw-Hill. pp. 17–19. ISBN 978-0-07-338314-9.
- Durbin, John R. (1992). Modern Algebra : an Introduction (3rd ed.). New York: Wiley. p. 63. ISBN 0-471-51001-7.
- Haining Fan; Ming Gu; Jiaguang Sun; Kwok-Yan Lam (2012). "Obtaining More Karatsuba-Like Formulae over the Binary Field". IET Information Security. 6 (1): 14–19. CiteSeerX 10.1.1.215.1576. doi:10.1049/iet-ifs.2010.0114.
- Rotman 2006, p. 267
- Fraleigh 1993, p. 376