Division theoremEuclidean division is based on the following result, which is sometimes called Euclid's division lemma. Given two integers and , with , there exist Uniqueness quantification, unique integers and such that : and :, where denotes the absolute value of . In the above theorem, each of the four integers has a name of its own: is called the , is called the , is called the and is called the . The computation of the quotient and the remainder from the dividend and the divisor is called or — in case of ambiguity — . The theorem is frequently referred to as the (although it is a theorem and not an algorithm), because its proof as given below lends itself to a simple division algorithm for computing and (see the section #Proof, Proof for more). Division is not defined in the case where ; see division by zero. For the remainder and the modulo operation, there are conventions other than , see .
HistoryAlthough "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 algorithm#Division by repeated subtraction, 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. Presently, most division algorithms, including long division, are based on this notation or its variants, such as binary numerals. A notable exception is Newton–Raphson division, which is independent from any numeral system. 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 (mathematics), division of numbers.
Intuitive exampleSuppose 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 total. 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 and the number of people is denoted '''', then one can divide the pie evenly among the people such that each person receives '''' slices (the quotient), with some number of slices being the leftover (the remainder). In which case, the equation holds. As an alternate example, if 9 slices were divided among 3 people instead of 4, then each would receive 3 and no slice would be left over, which means that the remainder would be zero, leading to the conclusion that 3 ''evenly divides'' 9, or that 3 ''divides'' 9. 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.
Examples*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.
ProofThe following proof of the division theorem relies on the fact that a decreasing sequence of non-negative integers stops eventually. It is separated into two parts: one for existence and another for uniqueness of '''' and ''''. Other proofs use the well-ordering principle (i.e., the assertion that every nonempty set, non-empty set of nonnegative integers, 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 for more).
ExistenceConsider first the case . Setting and , the equation may be rewritten as and the inequality may be rewritten as . This reduces the existence for the case to that of the case . Similarly, if and , setting , , and , the equation may be rewritten as , and the inequality may be rewritten as . Thus the proof of the existence is reduced to the case and — which will be considered in the remainder of the proof. Let and , then these are non-negative numbers such that . If then the division is complete, so suppose . Then defining and , one has with . As there are only non-negative integers less than , one only needs to repeat this process at most times to reach the final quotient and the remainder. That is, there exist a natural number such that and . This proves the existence and also gives a simple division algorithm for computing the quotient and the remainder. However, this algorithm is not efficient, since its number of steps is of the order of .
UniquenessThe pair of integers and such that is unique, in the sense that there can't be other pair of integers that satisfies the same condition in the Euclidean division theorem. In other words, if we have another division of by , say with , then we must have that :. To prove this statement, we first start with the assumptions that : : : : Subtracting the two equations yields :. So is a divisor of . As : by the above inequalities, one gets :, and :. Since , we get that and , which proves the uniqueness part of the Euclidean division theorem.
EffectivenessIn 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. In terms of decimal notation, long division provides a much more efficient algorithm for solving Euclidean divisions. Its generalization to Binary number, binary and hexadecimal notation provides further flexibility and possibility for computer implementation. However, for large inputs, algorithms that reduce division to multiplication, such as Division algorithm#Newton–Raphson division, 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).
VariantsThe Euclidean division admits a number of variants, some of which are listed below.
Other intervals for the remainderIn Euclidean division with as divisor, the remainder is supposed to belong to the interval (mathematics), interval of length . Any other interval of the same length may be used. More precisely, given integers , , with , there exist unique integers and with such that . In particular, if then . This division is called the ''centered division'', and its remainder is called the ''centered remainder'' or the least absolute remainder''. This is used for approximating real numbers: Euclidean division defines truncation, and centered division defines rounding.
Montgomery divisionGiven integers , and with and let be the modular multiplicative inverse of (i.e.,