6.1 Divisibility

One of the core properties of the integers is the division algorithm. This states that for a pair of integers $a$ and $b$, with $b\neq 0$, there is a unique quotient, $q$, and remainder, $r$, associated to them.

Theorem 6.1 (The Division Algorithm for Integers) If $a$ and $b$ are integers with $b>0$, then there are unique integers $q$ and $r$ such that \[a=bq+r, \quad \mbox{with } 0\leq r <b.\]

This theorem is an example of a uniqueness and existence statement. There are many theorems in mathematics where we prove that something exists (even though we may not know how to find it). For example, the Intermediate Value Theorem in calculus states that if $f:[a,b]\rightarrow \mathbb{R}$ is a continuous function and if $L$ is between $f(a)$ and $f(b)$, then there is exists a point in the domain of $f$ that maps to $L$. With this Intermediate Value Theorem, there may be many points that map to $L$. So, this is not a uniqueness statement. In the division algorithm, we are proving that the quotient and remainder both exist and are unique (there are no other numbers that satisfy the properties).

Proof. Let $a$ and $b$ be integers with $b>0$. We will first prove the existence of integers $q$ and $r$ such that \[a=bq+r, \quad \mbox{with } 0\leq r <b\] and then prove that these integers are unique.

Existence. If $a\geq 0$, then we can let \[S= \left\{ a-kb \: \vert \: a-kb\geq 0 \mbox{ and $k$ is a non-negative integer}\right\}.\] Since $a\geq 0$, we see that $a=a-0\cdot b$ is an element of $S$ and so $S$ is non-empty. We also see that $S \subseteq [0,a]$.

So by the Well-Ordering Property of the Integers, there is a smallest element of $S$ which we will call $r$. Since $r\in S$, there exists a non-negative integer $q$ such that $r=a-qb$.

Since $r$ is the smallest element of $S$ and since $a-(q+1)b<a-qb=r$, we see that $a-(q+1)b<0$, otherwise it would be a smaller element of $S$.

This implies that $r=a-qb<b$. Therefore we have the existence of the $q$ and $r$.

If $a<0$, using the above process we can find non-negative integers $q$ and $r$, with $0\leq r<b$, such that $-a=bq+r$. So $a=b(-q)+r$ satisfies the existence statement.
Uniqueness. In order to prove the uniqueness of the quotient and remainder, we assume that there are two pairs of integers $(q_1,r_1)$ and $(q_2,r_2)$ such that \[a= b q_1 + r_1 \mbox{ and } a= b q_2 + r_2, \mbox{ with } 0\leq r_1<b \mbox{ and } 0\leq r_2 <b.\] This implies that $b q_1 + r_1 = b q_2 + r_2$ and by rearranging the terms we have that \[b (q_1 - q_2) = r_2-r_1.\] If $0 \leq r_1 \leq r_2<b$, then $0 \leq b(q_1-q_2)=r_2-r_1<b$. So $q_1-q_2$ is an integer in $[0,1)$ and so must be $0$. Therefore, $q_1=q_2$ and so $r_1=r_2$. Therefore, the quotient and remainder are unique.

With the division algorithm, for each natural number $n>1$ we can partition the integers into equivalence classes based on the remainder when divided by $n$. For example, for $n=2$ we see that any integer belongs to one of the following sets: \[\left\{m\in \mathbb{Z} \: \vert \: m=2k \mbox{ for some } k\in \mathbb{Z} \right\} \quad \mbox{or} \quad \left\{m\in \mathbb{Z} \: \vert \: m=2k+1 \mbox{ for some } k\in \mathbb{Z} \right\},\] the even and odd integers.

In the following, we will focus on the set \[\left\{ m\in \mathbb{Z} \: \vert \: m=nk \mbox{ for some } k\in \mathbb{Z} \right\}.\]

Definition 6.1 Let $a$ and $b$ be integers with $b\neq 0$. We say that that $a$ is divisible by $b$, or $a$ is a multiple of $b$, if there exists a unique $q\in \mathbb{Z}$ such that $a=bq$.

We see in the next theorem that this property of divisibility by an integer is additive.

Theorem 6.2 Let $a$ and $b$ be integers that are each divisible by an integer $m\neq 0$. Then $a+b$ is divisible by $m$.

Proof. If $a$ and $b$ are divisible by an integer $m$, we have that there are integers $j$ and $k$ such that $a=mj$ and $b=mk$. So $a+b=mj+mk=m(j+k)$ and so $a+b$ is divisible by $m$.

We also see that if $a$ is divisible by $b$, then $-a$ is also divisible by $b$.

6.1.1 Divisibility Tests

As students develop fluency with multiplication of integers they often use certain tests to determine divisibility by certain numbers. The most common are given below.

Divisibility by 2. An integer is divisible by $2$ if and only if the last digit is $0$, $2$, $4$, $6$, or $8$.
Divisibility by 3. An integer is divisible by $3$ if and only if the sum of the digits of the integer is divisible by $3$.
Divisibility by 4. An integer is divisible by $4$ if and only if the last two digits of the number is divisible by $4$.
Divisibility by 5. An integer is divisible by $5$ if and only if the last digit is $0$ or $5$.
Divisibility by 6. An integer is divisible by $6$ if and only if the number is divisible by both $2$ and $3$.
Divisibility by 9. An integer is divisible by $9$ if and only if the sum of the digits of the integer is divisible by $9$.
Divisibility by 10. An integer is divisible by $10$ if and only if the last digit is $0$.
Divisibility by 11. An integer is divisible by $11$ if and only if the alternating sum of the digits is divisible by $11$. For example, $143$ is divisible by $11$ because $3-4+1=0$ and so is divisible by $11$.

We notice that all of these divisibility rules are based on the digits of the integer. So, in order to understand why these rules work, we need a way to denote an integer by its digits. Since we are using a base 10 notation of the integers, we can see that each integer has a unique representation of the form \[d_0 \cdot 10^0 + d_1 \cdot 10^1 + d_2 \cdot 10^2+ \ldots + d_n \cdot 10^n,\] with each of the $d_i\in \{0,1,2,3,4,5,6,7,8,9\}$ and the integer usually written with the digits in the reverse order. For example, \[235,609 = 9\cdot 10^0 + 0\cdot 10^1 + 6 \cdot 10^2 + 5 \cdot 10^3 + 3 \cdot 10^4 + 2 \cdot 10^5.\]

So in order to understand the divisibility by 5, we can see that a number $n$ can be written as \[\begin{align*} n &= d_0 \cdot 10^0 + d_1 \cdot 10^1 + d_2 \cdot 10^2+ \cdots + d_n \cdot 10^n \\ &= d_0 + 10 \cdot \left(d_1 \cdot 10^0 + d_2 \cdot 10^1+ \cdots + d_n \cdot 10^{n-1}\right) \\ &= d_0 + 5\cdot \left(2\cdot \left(d_1 \cdot 10^0 + d_2 \cdot 10^1+ \cdots + d_n \cdot 10^{n-1}\right) \right) \end{align*}\] and so $n$ is divisible by $5$ if and only if $d_0$ is divisible by $5$. And we have our result because the only digits divisible by $5$ are $0$ and $5$.

Understanding the reasoning behind the rules of divisibility by 3 and 9 are a little different. Each of these rules are based on \[10^n -1 = 9+9\cdot 10^1 + \cdots + 9\cdot 10^{n-1}= 9\cdot \left(1+1\cdot 10^1 + \cdots + 1\cdot 10^{n-1}\right),\] and so $10^n-1$ is divisible by $9$. The first few of these are $10-1=9$, $10^2-1=99=9\cdot 11$, $10^3-1=999=9\cdot 111$. So the number $n$ can be written as \[\begin{align*} n &= d_0 \cdot 10^0 + d_1 \cdot 10^1 + d_2 \cdot 10^2+ \cdots + d_n \cdot 10^n \\ &= d_0 + d_1 \cdot (10^1 -1 +1) + d_2 \cdot (10^2-1+1) + \cdots + d_n \cdot (10^n-1+1) \\ &= d_0 + d_1 \cdot (10^1-1) + d_1 + d_2 \cdot (10^2-1) + d_2 + \cdots + d_n \cdot (10^n-1) + d_n \\ &= \left(d_0 + d_1+ \cdots + d_n \right) + \left( d_1 \cdot (10^1-1) + d_2 \cdot (10^2-1) + \cdots + d_n \cdot (10^n-1) \right). \end{align*}\] Since each of the $d_i \cdot(10^i-1)$ are divisible by $9$, and hence divisible by $3$, we see that $n$ is divisible by $9$ or $3$ if and only if $\left(d_0 + d_1+ \cdots + d_n \right)$ is divisible by $9$ or $3$.

For each of these divisibility rules, we see that the relationship of the integer to the base of 10 is the key component. This relationship is explored further in the exercises by studying similar rules for a base 12 system.

6.1.2 Exercises

Prove the divisibility by 4 property.
Prove the divisibility by 6 property.
Prove the divisibility by 11 property.
Create divisibility tests in Base 12 that correspond to those given in this section for Base 10.
1. Divisibility by 2 in Base 12
2. Divisibility by 3 in Base 12
3. Divisibility by 4 in Base 12
4. Divisibility by 6 in Base 12
5. Divisibility by 10 in Base 12
6. Divisibility by 11 in Base 12