Euclidean division
In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than the absolute value of the divisor.
A fundamental property is that the quotient and the remainder exist and are unique, under some conditions.
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,[1] and modular arithmetic, for which only remainders are considered.
Although originally restricted to integers, Euclidean division and the division theorem can be generalized to univariate polynomials over a field and to Euclidean domains.
In the case of univariate polynomials, the main difference is that the inequalities
The uniqueness of the quotient and the remainder remains true for polynomials, but it is false in general.
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.
[citation needed] 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.
A notable exception is Newton–Raphson division, which is independent from any numeral system.
[citation needed] Suppose that a pie has 9 slices and they are to be divided evenly among 4 people.
, then one can divide the pie evenly among the people such that each person receives
Euclidean division can also be extended to negative dividend (or negative divisor) using the same formula; for example −9 = 4 × (−3) + 3, which means that −9 divided by 4 is −3 with remainder 3.
The following proof of the division theorem relies on the fact that a decreasing sequence of non-negative integers stops eventually.
Other proofs use the well-ordering principle (i.e., the assertion that every non-empty set of non-negative integers has a smallest element) to make the reasoning simpler, but have the disadvantage of not providing directly an algorithm for solving the division (see § Effectiveness for more).
[5] For proving the existence of Euclidean division, one can suppose
This provides also an algorithm for computing the quotient and the remainder, by starting from
However, this algorithm is not efficient, since its number of steps is of the order of
The pair of integers r and q such that a = bq + r is unique, in the sense that there can be no other pair of integers that satisfy the same condition in the Euclidean division theorem.
In other words, if we have another division of a by b, say a = bq' + r' with 0 ≤ r' < |b|, then we must have that To prove this statement, we first start with the assumptions that Subtracting the two equations yields So b is a divisor of r′ – r. As by the above inequalities, one gets and Since b ≠ 0, we get that r = r′ and q = q′, which proves the uniqueness part of the Euclidean division theorem.
In general, an existence proof does not provide an algorithm for computing the existing quotient and remainder, but the above proof does immediately provide an algorithm (see Division algorithm#Division by repeated subtraction), even though it is not a very efficient one as it requires as many steps as the size of the quotient.
This is related to the fact that it uses only additions, subtractions and comparisons of integers, without involving multiplication, nor any particular representation of the integers such as decimal notation.
Its generalization to binary and hexadecimal notation provides further flexibility and possibility for computer implementation.
However, for large inputs, algorithms that reduce division to multiplication, such as Newton–Raphson, are usually preferred, because they only 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 (for more, see Division algorithm#Fast division methods).
The Euclidean division admits a number of variants, some of which are listed below.
In Euclidean division with d as divisor, the remainder is supposed to belong to the interval [0, d) of length |d|.
This is used for approximating real numbers: Euclidean division defines truncation, and centered division defines rounding.
This result generalizes Hensel's odd division (1900).
[1] 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.
