The division algorithm is the conceptual underpinning of many concepts in number theory (congruence arithmetic is one example). In this post, we present a proof of the division algorithm and connect it to one important property of congruence.
This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.
The Division Algorithm
The following is the statement of the division algorithm.
Let and be positive integers. Then there exist unique integers and such that
Let be the set . Let be the following subset of .
The set is a set of non-negative integers. Hence it must have a least element, say . Then we have for some positive integer . Furthermore, we have . If , would not be the least element of since we can subtract into to obtain , which is less than and is an element of .
We now have found integers and such that . It remains to show that the integers and are unique. Suppose there are also integers and such that
After subtracting, . Since divides both and , must divides . This means that , since both and are non-negative integers that are less than . Thus and in turns .
Conceptually the division algorithm tells us that there is a unique remainder upon division of by . In terms of actual computation, it does not tell us how to find the remainder or the quotient. However it is the conceptual underpinning of many concepts and ideas in number theory.
We now use the division algorithm to prove one important property of congruence. The symbol means that divides (in words, we say is congruent to modulo ). For a basic discussion of congruence arithmetic, see “A basic discussion of congruences”. We prove the following property of congruence.
For every integer , for a unique integer with .
In other words, any integer is congruence modulo to one and only one element in the set . The integer is called the least residue of modulo .
The above property about least residue follows from the division algorithm. Let be any integer. If , clearly . We can assume that .
Now consider the case that . By the division algorithm, there are integers and such that where . Thus .
Consider the case that . By the division algorithm, there are integers and such that where . Immediately we have . Thus . Note that . Thus /
One concluding remark is that any least residue that is found in the above argument is unique. This is because no two distinct elements of the set can be congruent to each other.