The Division Algorithm

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 a and b be positive integers. Then there exist unique integers q and r such that

      a = q \cdot b + r

    where 0 \le r <b.

Let A be the set A=\left\{a-jb: j=0,1,2,3,\cdots \right\}. Let A_+ be the following subset of A.

    A_+=\left\{x \in A: x \ge 0 \right\}

The set A_+ is a set of non-negative integers. Hence it must have a least element, say r. Then we have r=a-qb for some positive integer q. Furthermore, we have 0 \le r<b. If r>b, r would not be the least element of A_+ since we can subtract b into r to obtain a-(q+1)b, which is less than r and is an element of A_+.

We now have found integers q and r such that a = q \cdot b + r. It remains to show that the integers q and r are unique. Suppose there are also integers q_0 and r_0 such that

    a=q \cdot b + r=q_0 \cdot b + r_0

After subtracting, (q-q_0) \cdot b + (r-r_0)=0. Since b divides both 0 and (q-q_0) \cdot b, b must divides r-r_0. This means that r-r_0=0, since both r and r_0 are non-negative integers that are less than b. Thus r=r_0 and in turns q-q_0. \blacksquare

Conceptually the division algorithm tells us that there is a unique remainder r upon division of a by b. 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.


___________________________________________________________________________________________________________________

Congruence

We now use the division algorithm to prove one important property of congruence. The symbol a \equiv b \ (\text{mod} \ m) means that m divides a-b (in words, we say a is congruent to b modulo m). For a basic discussion of congruence arithmetic, see “A basic discussion of congruences”. We prove the following property of congruence.

    For every integer a, a \equiv r \ (\text{mod} \ m) for a unique integer r with 0 \le r<m.

In other words, any integer is congruence modulo m to one and only one element r in the set \left\{0,1,2,\cdots,m-1 \right\}. The integer r is called the least residue of a modulo m.

The above property about least residue follows from the division algorithm. Let a be any integer. If a=0, clearly a \equiv 0 \ (\text{mod} \ m). We can assume that a \ne 0.

Now consider the case that a>0. By the division algorithm, there are integers q and r such that a=q \cdot m+r where 0 \le r <m. Thus a \equiv r \ (\text{mod} \ m).

Consider the case that a<0. By the division algorithm, there are integers q and r such that -a=q \cdot m+r where 0 \le r <m. Immediately we have a=(-q) \cdot m+(-r). Thus a \equiv -r \ (\text{mod} \ m). Note that -r \equiv m-r \ (\text{mod} \ m). Thus a \equiv m-r \ (\text{mod} \ m)/

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 \left\{0,1,2,\cdots,m-1 \right\} can be congruent to each other. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s