Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Division algorithm

1 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. The integer q is the quotient, r is the remainder, d is the divisor, and a is the dividend.

2 Examples

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

3 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.

3.1 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 principle, there is a nonnegative integer n such that (−b)n ≥ −a, i.e. a − dn ≥ 0.
• If d > 0, then again by the Archimedean principle, 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.

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.

3.2 Uniqueness

Since r = a − qd, it is enough to prove the uniqueness of q. So, suppose there exist integers q and q' satisfying the result of the theorem. Then we must have 0 ≤ a − qd < |d| and 0 ≤ a − q'd < |d|. Note that

Together, these two inequalities show that (q' − q)d is an integer whose absolute value is strictly less than |d|. Since |d| > 0, division gives

Since q' − q is an integer, we must have q' − q = 0, i.e. q = q'. This completes the proof of the uniqueness of q and r.

4 Generalisations

There is nothing particular 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.

Politics	Business	Finance

Topics: Division Algorithm Minus Integer Integers I.e Nonnegative...

---

Division algebraRing theory In the field of mathematics called abstract algebra, a division algebra is, roughly speaking, an algebra over a field in which division is possible. Definitions Formally, we start with an algebra D over a field, and assume that D does not just Division of labourDivision of labour is the breakdown of labour into specific, circumscribed tasks for maximum efficiency of output in the context of manufacturing. It is the cardinal aspect of production. It can also be the fragmenting or reduction of human activity into Division ringIn abstract algebra, a division ring also called a skew field is a ring with 0 ≠ 1 and such that every non-zero element a has a multiplicative inverse (i. an element x with ax xa 1). Division rings are very similar to fields except that their multiplic DivisionThis article is about the arithmetic operation. For other uses, see Division (disambiguation). In mathematics, especially elementary arithmetic, division is an arithmetic operation which is the reverse operation of multiplication and sometimes can be inte Division (biology)This article discusses categorisations of organisms. For a different meaning in biology, see cell division. In biology, the equivalent of a phylum in the plant or fungi kingdom is called a division . The main plant divisions, in the order in which they pr Division (disambiguation)Division is a term used in several different contexts: In mathematics, division forms the opposite operation to multiplication. In the military, a division is a unit, typically consisting of from 10,000 to 20,000 troops. In enterprise management, a divisi Division by two Division (military) Division by zero Division of property Divisions of Bangladesh Division (sport) Division of Korea Division of the house Division of the field