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

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

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 . 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 . 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}$

# A basic discussion of congruences

When performing the division $45 \div 7$, the remainder is $3$. What is the remainder in the division $9664^{79081} \div 55049$? What is the remainder in the division of $(2^{57885161} - 1)$ by $524287$? If you have special software, you can determine quickly that the remainder for the first question is the number $1020$. Note that the number $2^{57885161} - 1$ in the second question is the current largest known prime number at the writing of this post. The special software you use might have to struggle a little to come up with the answer of $255$. Without special software, you can use congruence arithmetic to perform the above calculations.

Congruence notation was invented by the great mathematician Carl Friedrich Gauss (1777 – 1855). It is hard to overstate the importance of the role of congruence in number theory. The notion not only eases calculation but also makes statements of theorems much easier to state and simplifies the proofs of theorems. This post is a basic discussion of congruence.

For more information about congruence or modular arithmetic, see the number theory introductory text [1] or the Wikepedia entry on modular arithmetic.

___________________________________________________________________________________________________________________

Basic Discussion

Given integers $a$, $b$ and $m$ with $m>0$, the statement that $a$ is congruent to $b$ modulo $m$ means that the difference $a-b$ is divisible by $m$. In symbol, we write $a \equiv b \ (\text{mod} \ m)$. The number $m$ is the modulus of the congruence. We also use the notation $m \lvert a-b$ to refers to the statement that $a-b$ is divisible by $m$. We repeat the definition below.

$a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \ m \lvert a-b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The following two properties of congruence that can be easily verified from definition $(1)$.

$a \equiv b \ (\text{mod} \ m) \ \ \ \Longleftrightarrow \ \ \ a=b+k \cdot m \text{ for some integer } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2a)$

$b+k \cdot m \equiv b \ (\text{mod} \ m) \text{ for all integers } k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2b)$

Another meaning of congruence modulo $m$ comes from the division algorithm. For example, the division $45 \div 7$ gives the remainder $3$, i.e., $45=6 \cdot 7 +3$. So for the division $a \div m$ where both $a$ and $m$ are both positive, we have $a=q \cdot m+r$ for some integer $r$ with $0 \le r (call the remainder) and some integer $q$. From this we can conclude that every integer $a$ is congruent modulo $m$ to exactly one integer from the set $\left\{0,1,2,\cdots,m-1 \right\}$. The integer $r$ is called the least residue of $a$ modulo $m$. We summarize as follows: for every integer $a$,

$a \equiv r \ (\text{mod} \ m) \text{ for a unique integer } r \text{ with } 0 \le r < m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

For a proof of property (3), see this post. Another characteristic of congruence modulo $m$ is the following property.

$a \equiv b \ (\text{mod} \ m) \Longleftrightarrow \text{ each of } a \text{ and } b \text{ leaves the same remainder }$

$\text{ when divided by } m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

All the above conditions point to the cyclical nature of congruence, which can be visualized in a diagram. The figure is below describes congruence modulo $12$.

You can start at any point in the above diagram. Every time you add or subtract the modulus $m=12$, you go around the circle and come back to the same point you start from (conditions 2 and 4). Two integers are related congruence modulo $12$ if they can be reduced by the division algorithm to the same time in the clock (condition 3).

___________________________________________________________________________________________________________________

Some Properties for Congruence

Congruence arithmetic is similar to conventional arithmetic. However, there are important differences. For example, comparing congruence with the equality sign = will help us see some of the differences. To set up the comparison, the following are some operations on real numbers we would like to focus on:

Operations on real numbers:

$a=b \ \ \Longrightarrow \ \ b=a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R1}$

$a=b \text{ and } b=c \ \ \Longrightarrow \ \ a=c \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R2}$

$a=b \text{ and } c=d \ \ \Longrightarrow \ \ a+c=b+d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R3}$

$a=b \text{ and } c=d \ \ \Longrightarrow \ \ a \cdot c=b \cdot d \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R4}$

$ac=bc \text{ and } c \ne 0 \ \ \Longrightarrow \ \ a=b \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{R5}$

All the above arithmetic operations on real numbers have analog in congruence except for R5. The following are the equivalence in congruence operations.

$a \equiv b \ (\text{mod} \ m) \ \ \Longrightarrow \ \ b \equiv a \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C1}$

$a \equiv b \ (\text{mod} \ m) \text{ and } b \equiv c \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv c \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C2}$

$a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a+c \equiv b+d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C3}$

$a \equiv b \ (\text{mod} \ m) \text{ and } c \equiv d \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \cdot c \equiv b \cdot d \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C4}$

$a \cdot c \equiv b \cdot c \ (\text{mod} \ m) \text{ and } c \not \equiv 0 \ (\text{mod} \ m) \ \ \Longrightarrow \ \ a \equiv b \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{C5}$

C5 has the additional requirement that $c$ and the modulus $m$ are coprime.

The properties C3 and C4 indicate that congruences may be validly added, subtracted and multiplied.

Note that the direct analog of R5 is not true in general. For example, $20 \equiv 2 \ (\text{mod} \ 6)$. However, $10 \not \equiv 1 (\text{mod} \ 6)$. In this case we cannot cancel out the common factor of $2$ on both sides of the congruence. When the additional requirement that the common factor $c$ and the modulus $m$ are coprime (i.e. the greatest common divisor is $1$), we can cancel out the common factor (as indicated by C5).

The derivation of the properties C1 through C4 is straightforward. The proof of C5 relies on Euclid’s lemma.

___________________________________________________________________________________________________________________

Some Examples

The properties in the above section are not meant to be memorized. The best approach is to work examples.

One typical congruence calculation is to find the least residue of a number $a$ modulo $m$. The number $a$ could be a sum or a product. Or it could be some number raised to an exponent. For the case of sum or product, we can start by reducing the components in the sum or product. For the case of an exponential, we can sometimes break it up into product of smaller numbers or use a “divide and conquer” approach. Let’s look at some examples.

To find $55 \cdot 67$ congruence modulo $7$, we do not need to first multiply. We can start by reducing each of the factors as follows:

$55 \cdot 67 \equiv 6 \cdot 4 \equiv 24 \equiv 3 \ (\text{mod} \ 7)$

In the above calculation we use property C4. We have $55 \equiv 6 \ (\text{mod} \ 7)$ and $67 \equiv 4 \ (\text{mod} \ 7)$. Thus $55 \cdot 67 \equiv 6 \cdot 4 \ (\text{mod} \ 7)$. We really do not need to be too conscious of which property to use. Just work enough examples and the process will flow quite naturally.

To find $1567 \equiv (\text{mod} \ 13)$, we can start by breaking up the number $1567$. The following is one example of how to do so.

\displaystyle \begin{aligned} 1567&=30 \cdot 50 + 67 \\&=31 \cdot 50 + 17 \\&\equiv 5 \cdot 11+4=59 \ (\text{mod} \ 13)\\&=50+9 \\&\equiv 11+9 \ (\text{mod} \ 13)=20 \\&\equiv 7 \ (\text{mod} \ 13) \end{aligned}

In the above calculation, we break up $1567$ into multiple of $50$ with $17$ added. Then starting reducing each of the numbers. Then multiply and sum to get $59$. We then break it up into $50$ and $9$, which is reduced into $11$ and $9$. Finally $20$ is reduced into $7$ modulo $13$. The properties used are C3 and C4. Once again, this type of calculation will flow naturally after working a few examples.

To find $55^{23} \equiv (\text{mod} \ 7)$, we can start by reducing the base $55$.

\displaystyle \begin{aligned} 55^{23}&\equiv 6^{23} \ (\text{mod} \ 7) \\&=(6^2)^{11} \cdot 6 \\&\equiv (1)^{11} \cdot 6 \ (\text{mod} \ 7) \\&\equiv 6 \ (\text{mod} \ 7) \end{aligned}

It follows from property C4 that if $a \equiv b \ (\text{mod} \ m)$, then $a^n \equiv b^n \ (\text{mod} \ m)$. Based on this idea, we can reduce base $55$ to the smaller base of $6$. We then reduce the exponent $23$ to the exponent of $11$. Such a process is a “divide and conquer” process that repeatedly reduces the exponent by half down to a manageable size.

Another example. Find the $2^{100} \equiv (\text{mod} \ 101)$. Note that $2^7=128$ and $128 \equiv 27 \ (\text{mod} \ 101)$.

\displaystyle \begin{aligned} 2^{100}&= (2^{7})^{14} \cdot 2^2 \\&\equiv (27)^{14} \cdot 4 \ (\text{mod} \ 101) \\&= (27^2)^{7} \cdot 4 \\&\equiv 22^7 \cdot 4 \ (\text{mod} \ 101) \\&=(22^2)^3 \cdot 22 \cdot 4 \\&\equiv 80^3 \cdot 88 \ (\text{mod} \ 101) \\&=80^2 \cdot 80 \cdot 88 \\&\equiv 37 \cdot 80 \cdot 88 \ (\text{mod} \ 101) \\&=2960 \cdot 88 \\&\equiv 31 \cdot 88 \ (\text{mod} \ 101) \\&\equiv 1 \ (\text{mod} \ 101) \end{aligned}

The key to a reduction of power in a congruence calculation is to find the right starting point. In the above example, exponent is reduced from $100$ to $14$, Then subsequently, keep reducing the exponent by half in each step until reaching a size that is manageable or easy to do.

It also follows from Fermat’s little theorem that $2^{100} \equiv 1 \ (\text{mod} \ 101)$.

___________________________________________________________________________________________________________________

More Examples

It is well known, even to some elementary school children, that an integer is divisible by nine if the sum of the digits is divisible by nine. The proof of this fact is very easy if done using congruence. The idea for the proof will be clear from the following example.

The number $55953$ is divisible by nine since $55953 = 9 \cdot 6217$. Also note that the sum of its digits is $27$. We can also look at the congruence angle. First, $10 \equiv 1 \ (\text{mod} \ 9)$, $10^2 \equiv 1 \ (\text{mod} \ 9)$ and $10^3 \equiv 1 \ (\text{mod} \ 9)$ and so on. Furthermore, we have:

$55953=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3$

We can now reduce the digital representation of $55953$ using congruence.

\displaystyle \begin{aligned} 55953&=5 \cdot 10^5+5 \cdot 10^3+9 \cdot 10^2+5 \cdot 10+3 \\&\equiv 5 \cdot 1+5 \cdot 1+9 \cdot 1+5 \cdot 1+3 \\&=27 \\&\equiv 0 \ (\text{mod} \ 9) \end{aligned}

The above derivation shows that any positive integer is congruent modulo $9$ to the sum of its digits. Thus a positive integer is divisible by $9$ if and only if the sum of its digits is divisible by $9$.

The same property is also true for divisibility by three. Using congruence, it can be shown that any positive integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$.

Congruence modulo $11$ is an interesting case. Note that $10 \equiv -1 \ (\text{mod} \ 11)$, $10^2 \equiv 1 \ (\text{mod} \ 11)$, and $10^3 \equiv -1 \ (\text{mod} \ 11)$ and so on. Thus $10^n \equiv k \ (\text{mod} \ 11)$ where $k=1$ or $k=-1$ depending on whether the power is even or odd. So in reducing the digital representation of a number, we need to add alternating plus and minus signs.

\displaystyle \begin{aligned} 85647&=8 \cdot 10^4+5 \cdot 10^3+6 \cdot 10^2+4 \cdot 10+7 \\&\equiv 8 \cdot 1+5 \cdot (-1)+6 \cdot 1+4 \cdot (-1)+7 \\&=12 \\&\equiv 1 \ (\text{mod} \ 11) \end{aligned}

Thus $85647$ is not divisible by $11$.

___________________________________________________________________________________________________________________

Exercises

Work the two congruence calculation mentioned at the beginning of the post. Show the following.

$9664^{79081} \equiv 1020 \ (\text{mod} \ 55049)$

$2^{57885161}-1 \equiv 255 \ (\text{mod} \ 524287)$

___________________________________________________________________________________________________________________

Reference

1. Dudley U., Elementary Number Theory, 2nd ed., Dover Publications, Inc, New York, 2008

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$