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

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

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

**Second proof of Division algorithm**: Consider the set

About 200 years ago in Germany, at the age of 23 C. F. Gauss ^{1.1}published **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

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

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.

- ,
- ,
- for any integers and , and
- .

David Joyner 2007-09-03