Main Index Number Theory Arithmetics Multiplication Divisibility
 Subject Index
comment on the page

Division algorithm

This is a name of a theorem on which important algorithms of number theory are based. Dedekind said about this result This is the basis of the whole number theory  (Dies ist die Grundlage aller Zahlentheorie.  ([1] , p. 514, footnote) ).

Division Algorithm (Standard form): Given two integers typeset structure and typeset structure, typeset structure, there exist unique integers typeset structure and typeset structure such that

FormBox[RowBox[{RowBox[{a, =, RowBox[{q d + r       and        0 <= r <, |, d, |, Cell[]}]}], ,}], TraditionalForm](1)

where typeset structure denotes the absolute value of  typeset structure.

The integer typeset structure is called the quotient, typeset structure the remainder, typeset structure the divisor and typeset structure the dividend.

To prove this consider the sequence

..., a - 3 d, a - 2 d, a - d, a, a + d, a + 2 d, a + 3 d, ...(2)

Let typeset structure denote the least non-negative integer in this sequence, say typeset structure. If typeset structure, then the previous term of the sequence is non-negative and typeset structure, a contradiction with the minimality of typeset structure.  This proves the existence of typeset structure and typeset structure.

To prove the uniqueness suppose that typeset structure. If typeset structure then trivially also typeset structure. Suppose that typeset structure. Then typeset structure. Consequently, typeset structure divides the difference typeset structure. Without loss of generality we can suppose that typeset structure.

If typeset structure then typeset structure and typeset structure, and so typeset structure. If typeset structure then typeset structure and similarly typeset structure, and so typeset structure. Combining both results we proved that typeset structure. Since simultaneously typeset structure divides typeset structure, typeset structure, i.e. typeset structure. If this is true then substituting this into typeset structure immediately yields typeset structure, or that typeset structure (note typeset structure). QED

The above proof result tacitly required application of two fundamental properties of positive integers: of the Archimedean property and of the well-ordering principle. By the Archimedean property there is a non-negative integer typeset structure such that typeset structure. If typeset structure then typeset structure, and if typeset structure then typeset structure and the sequence (1) contains a non-negative element in either case. On the other hand the well-ordering principle applies that (1) contains a least non-negative element typeset structure.

Since the integers typeset structure form a complete residue system modulo typeset structure, the above ideas can be used to prove a more general result:

Division Algorithm (General form): Given two integers typeset structure and typeset structure, typeset structure and a complete residue system typeset structure modulo typeset structure, there exist unique integers typeset structure and typeset structure such that

a = q d + r _ i .(3)

Two cases of this generalization might be of interest:

Division Algorithm (The least absolute residues form): Given two integers typeset structure and typeset structure, typeset structure, there exist unique integers typeset structure and typeset structure such that

a = q d + r,        -(| d |)/2 < r <= (| d |)/2 .(4)

Division Algorithm (The least non-positive residues form): Given two integers typeset structure and typeset structure, typeset structure, there exist unique integers typeset structure and typeset structure such that

FormBox[RowBox[{a, =, RowBox[{q d + r       and     -, |, d, |, RowBox[{<, r, <=, RowBox[{0, RowBox[{Cell[], .}]}]}]}]}], TraditionalForm](5)

For a ring theoretic generalization see Euclidean rings  ↑ .

References

[1]  Dirichler, P. G. (1894). Vorlesungen über Zahlentheorie (Herausgegeben und mit Zusätzen versehen von R. Dedekind) IV. umegearbeitete und vermehrte Auflage. (Lectures on number theory. Edited and supplements added by R.Dedekind. Fourth rewritten and augmented edition). Braunschweig: F. Vieweg und Sohn.

Cite this web-page as:

Štefan Porubský: Division Algorithm.

Page created  .