## Division algorithm

The next result basically says that, for every integer occurs in one of the columns in the array (1.1) above. It also goes by the name long division''.

Theorem 1.2.7 (Division algorithm)   Let and be integers. There are integers (the quotient) and (the remainder) such that

Furthermore, and are unique.

Our proof of the division algorithm depends on the following axiom.

Axiom 1.2.8 (Well-ordering principle)   Each non-empty set of natural numbers contains a least element.

In particular, each set of integers which contains at least one non-negative element must contain a smallest non-negative element. Furthermore, this smallest element is unique.

We begin the proof of the division algorithm by showing that and are unique. Suppose , where , . Then . Since divides the right side and the first term of the left side of the above equation, must divide . But , so . Therefore is unique. Since , this in turn implies is also unique.

We present two proofs of the existence of and in the division algorithm.

First proof of Division algorithm: First, we claim that must lie in between some two consecutive elements of

say (see (1.1) for a visual representation of this idea). Then . Therefore, , where . This proves the division algorithm, assuming the truth of the claim (which is left as an exercise).

Second proof of Division algorithm: Consider the set

This contains at least one non-negative element, for example, . By the well-ordering principle, contains a least non-negative element, say . By definition of , there is an integer such that . It remains to show . Suppose not (to get a contradiction), i.e., suppose . Then , and , so was not the smallest non-negative element of . This contradiction shows that the hypothesis is false. Therefore and the proof is complete.

About 200 years ago in Germany, at the age of 23 C. F. Gauss 1.1published Disquisitiones Arithmeticae, essentially an expanded version of his PhD thesis, that revolutionized the study of number theory. One piece of new notation which Gauss introduced is the congruence or modulus notation. Let be integers. We say that is congruent to modulo , written

if . In this case, is called the modulus and is a residue of modulo .

The division algorithm may be restated in this new notation as follows.

Theorem 1.2.9   If and are integers then there is an integer satisfying

In other words, each integer has a residue mod (called the least residue) ) which is in the range . Furthermore, this residue can be computed using the division algorithm.

Example 1.2.10   We have
• ,
• ,
• for any integers and , and
• .

david joyner 2008-04-20