Division algorithm

From Wikipedia, the free encyclopedia

The division algorithm is a theorem in mathematics which precisely expresses the outcome of the usual process of division of integers. Its name is a partial misnomer: it is not a true algorithm (a well-defined procedure for achieving a specific task), but it can be used to find the greatest common divisor of two integers.

The term "division algorithm" is also used in algebra for a general variant of this theorem, shown to hold in integral domains which are principal ideal domains.

Contents 1 Statement of theorem 2 Examples 3 Proof 3.1 Existence 3.2 Uniqueness 4 Generalized division algorithm and b-parts of real numbers 4.1 Definition. 4.2 The generalized division algorithm. 4.3 Number theoretic explanation of b-Parts 5 Generalizations 6 External links

[edit] Statement of theorem

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

There exist 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 called the quotient
• r is called the remainder
• d is called the divisor
• a is called the dividend

[edit] 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.

[edit] Proof

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

[edit] 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.

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 implies a-qd ≥ d. This implies that a-qd-d ≥0, further implying that a-(q+1)d ≥ 0. Therefore, a-(q+1)d is in S and, since a-(q+1)d=r-d with d>0 we know a-(q+1)d<r, contradicting the assumption that r was the least nonnegative element of S.

• If d<0 then r ≥ -d implying that a-qd ≥ -d. This implies that a-qd+d ≥0, further implying that a-(q-1)d ≥ 0. Therefore, a-(q-1)d is in S and, since a-(q-1)d=r+d with d<0 we know a-(q-1)d<r, contradicting the assumption that r was the least nonnegative element of S.

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.

[edit] Uniqueness

Suppose there exists q, q' , r, r' with 0 ≤ r, r' < |d| such that a = dq + r and a = dq' + r' . Without loss of generality we may assume that q ≤ q' .

Subtracting the two equations yields: d(q' - q) = (r - r' ).

If d > 0 then r' ≤ r and r < d ≤ d+r' , and so (r-r' ) < d. Similarly, if d < 0 then r ≤ r' and r' < -d ≤ -d+r, and so -(r- r' ) < -d. Combining these yields |r- r' | < |d|.

The original equation implies that |d| divides |r- r' |; therefore either |d| ≤ |r- 'r' | or |r- r' |=0. Because we just established that |r-r' | < |d|, by trichotomy we may conclude that the first possibility cannot hold. Thus, r=r' .

Substituting this into the original two equations quickly yields dq = dq' and, since we assumed d is not 0, it must be the case that q = q' proving uniqueness.

[edit] Generalized division algorithm and b-parts of real numbers

Let a , b be positive integers. By the division algorithm we have a = bq + r where q , r are integers and . Also denote by [a] the largest integer not exceeding a and put (a) = (a)₁ = a − [a] that is decimal (or fractional) part of a and also is denoted by {a}. Then we have

Considering this fact, M.H.Hooshmand introduces the conception b-parts of real numbers and study their number theoretic and algebraic properties in ^[1] , ^[2] and ^[3].

[edit] Definition.

For every real numbers a and set

The notation [a]_b is called b-integer part of a and (a)_b b-decimal part of a. Also [a]_b and (a)_b are called b-parts of a.

Clearly a = [a]_b + (a)_b where

There after he states the generalized division algorithm and gives two proofs that one of them is based on the b-parts of real numbers.

[edit] The generalized division algorithm.

He states the following theorem in the papers and gives two different proofs for it:

For every real numbers a and , there exist a unique integer q and a unique non negative real number r such that

q and r are called integer quotient and b-bounded remainder of the division of a by b, respectively.

[edit] Number theoretic explanation of b-Parts

For every real numbers a and , if b > 0, then (a)_b is the same b-bounded remainder of the (generalized) division of a by b and [a]_b is the largest element of not exceeding a. Also if b < 0, then (a)_b is the inverse of the remainder of the division of − a by − b (because (a)_b = − ( − a) _{− b}) and [a]_b is the smallest element of not less than a.

For every positive integer b and real a, [a]_b is the same unique integer of the residue class (mode b) that is divisible by b (because ).

[edit] Generalizations

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.

[edit] External links

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

1. ^ M.H.Hooshmand, (2005). "b-Digital sequences". WMSCI 2005: 9TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS 8: 142-146. http://apps.isiknowledge.com/full_record.do?product=UA&search_mode=GeneralSearch&qid=1&SID=N1gDCAgALmD8dPO9IkD&page=1&doc=4&colname=ISIP. 
2. ^ M.H.Hooshmand and H.K Haili, (2008). "Some algebraic properties of b-parts of real numbers". Šiauliai Mathematical Seminar 3(11): 115-121. http://siauliaims.su.lt/article.al?id=116. 
3. ^ M.H.Hooshmand, (2001). "r-Bounded Groups and Characterization of Additive Subgroups of Real Numbers". Gulchin-I Riyazi (in farsi) 9(1): 49-58. http://dbase.irandoc.ac.ir/00690/00690749.htm.