The division algorithm is a theorem in mathematics which precisely expresses the outcome of the usual process of division of integers. The name is something of a misnomer, as it is a theorem, not an algorithm, i.e. a well-defined procedure for achieving a specific task — although the division algorithm can be used to find the greatest common divisor of two integers. A theorem is a proposition that has been or is to be proved on the basis of explicit assumptions. ... Euclid, detail from The School of Athens by Raphael. ... In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... Look up Misnomer in Wiktionary, the free dictionary. ... A theorem is a proposition that has been or is to be proved on the basis of explicit assumptions. ... Flowcharts are often used to represent algorithms. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are both not zero is the largest integer that divides both numbers. ...

Statement of theorem

Specifically, the division algorithm states that given two integers a and d, with d ≠ 0

There exists unique integers q and r such that a = qd + r and 0 ≤ r < | d |, where | d | denotes the absolute value of d. In mathematics, the absolute value (or modulus1) of a real number is its numerical value without regard to its sign. ...

The integer

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

Examples

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

Proof

The proof consists of two parts — first, the proof of the existence of q and r, and secondly, the proof of the uniqueness of q and r.

Existence

Consider the set

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

• If d < 0, then −d > 0, and by the Archimedean property, there is a nonnegative integer n such that (−d)n ≥ −a, i.e. a − dn ≥ 0.
• If d > 0, then again by the Archimedean property, there is a nonnegative integer n such that dn ≥ −a, i.e. a − d(−n) = a + dn ≥ 0.

In either case, we have shown that S contains a nonnegative integer. This means we can apply the well-ordering principle, and deduce that S contains a least nonnegative integer r. If we now let q = (a − r)/d, then q and r are integers and a = qd + r. In mathematics, the Archimedean property of an ordered algebraic structure, such as a linearly ordered group, and in particular of the real numbers, is the property of having no (non-zero) infinitesimals. ... Sometimes the phrase well-ordering principle (or the axiom of choice) is taken to be synonymous with well-ordering theorem. On other occasions the phrase is taken to mean the proposition that the set of natural numbers {1, 2, 3, ....} is well-ordered, i. ...

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

• If d > 0, then r = d. Let q' = q + 1; then q' is an integer and q'd = (q + 1)d = qd + d = qd + r = a, i.e. a − q'd = 0.
• If d < 0, then r = −d. Let q' = q − 1; then q' is an integer and q'd = (q − 1)d = qd − d = qd + r = a, i.e. a − q'd = 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 < |d|. This completes the proof of the existence of q and r.

Uniqueness

Suppose and r,R with such that a = dq + r and a = dQ + R.

Subtracting the two equations yields: d(Q − q) = (r − R) .

By divisibility rules, we have that since both sides are elements of integers, d must divide (r − R). However, − d < r − R < d and in this range, the only possible element satisfying this condition is 0. Hence r − R = 0 or r = R .

Substituting this into the original two equations quickly yields dq = dQ (Recall: d is not 0) and thus q = Q proving uniqueness.

Generalisations

There is nothing particularly special about the set of remainders {0, 1, ..., |d| − 1}. We could use any set of |d| integers, such that every integer is congruent to one of the integers in the set. This particular set of remainders is very convenient, but it is not the only choice. See also coset and equivalence relation. Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, if G is a group, H a subgroup of G, and g an element of G, then gH = { gh : h an element of H } is a left coset of H in G, and Hg = { hg : h an element of H } is a right coset of H in G... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...

External links

• Informal discussion of the division algorithm and well-ordering principle