$Project Greater Ed Logo$

Divisibility

Discrete Mathematics Divisibility and the Quotient-Remainder Theorem Divisibility

Divides

Let $n,m\in \mathbb{Z}$ . We say that $m$ divides $n$ , and write $m|n$ , if there exists a number $c\in \mathbb{Z}$ such that $n=c\cdot m$ .
If $m$ does NOT divide $n$ , we write $m\not|\ n$ .

There are several equivalent ways of stating the above definition. The most helpful way is “If I attempt to divide the number $n$ by $m$ and I get an integer, then $m$ (evenly) divides $n$ . Otherwise, $m$ does not divide $n$ .

Putting the above definition another, more verbal, way: “ $m$ divides $n$ if and only if $n$ can be written as a product of $m$ and some other integer.”

Note

To prove, show, verify, or support the claim that one number $m$ divides another number $n$ , by the definition above, one must find an integer $c$ such that $n=m\cdot c$ ; i.e. show that your $c$ times $m$ gives you $n$ .

Theorem

If $a,b$ and $c$ are integers such that $a|b$ and $b|c$ , then $a|c$ .

Proof: Since $a|b$ there is a $d_1\in \mathbb{Z}$ such that $b=ad_1$ . Similarly, since $b|c$ there is a $d_2\in \mathbb{Z}$ such that $c=bd_2$ . Substitution of the first equation into the second gives us

$\begin{align} c&=bd_2\\ &=(ad_1)d_2\\ &=a(d_1d_2)\end{align}$
and so,

$c$ is equal to some integer times

$a$ , implying that

$a|c$ .

Pro-Tip

When learning new definitions and theorems, try to first understand what the definition or theorem is saying, and then try to phrase it in your own words. If you can do that (correctly), then you probably fully understand the definition or theorem. Working examples helps with understanding as well, especially if you come up with your own.

Testing for Divisibility Tricks

Each of the boxes below explain a trick for determining whether a number $n$ is divisible by the given number.

The Test

A number $n$ is divisible by $2$ if (i.e. the 1’s digit) of $n$ is divisible by $2$ .

If $n=12436$ , $n$ is divisible by $2$ because the 1’s digit is $6$ which is clearly divisible by $2$ .

Because integers with more than one digit can be written as a sum of some multiple of $10$ plus a number less than $10$ . Since $2\vert 10$ , $2$ divides any multiple of $10$ , so we only need to check that $2$ divides the 1’s digit.

To see this reasoning through example, let $n=1378$ . Notice that $n=1378=1370+8$ . Notice also that $2\vert 1370$ (because $1370$ is a multiple of $10$ and $2\vert 10$ ), and $2\vert 8$ . Since each of these two added numbers is divisible by 2, so is the sum; i.e. so is $n$ .

The Test

A number $n$ is divisible by $3$ if the sum of the digits of $n$ is divisible by $3$ .

Note that if even after adding the digits the number is still too big, you can repeat the addition process until you have a number that is easy to test for divisibility by 3.

Let $n=5754$ . Then since the sum of the digits of $n$ is $21$ , and $21$ is divisible by $3$ , $n$ is also divisible by $3$ .

(See Modular Arithmetic lesson before reading this)

Note that $10\cong 1 (mod\ 3)$ . So, powers of $10$ such as $10,100,1000,$ etc. all have remainder $1$ when divided by $3$ .

So, if you have an integer with decimal representation $n=a_ka_{k-1}a_{k-2}\dots a_3a_2a_1a_0$ (i.e. the 1’s digit is $a_0$ the 10’s digit is $a_1$ etc.\) notice that

$a_k\cdot 10^k+a_{k-1}\cdot 10^{k-1}+\dots+a_2\cdot 100+a_1\cdot 10+a_0\equiv a_k+a_{k-1}+a_{k-2}+\dots+a_2+a_1+a_0\ (mod\ 3).$

Therefore, our number $n$ is divisible by $3$ if and only if the sum of our digits $a_k+a_{k-1}+a_{k-2}+\dots+a_2+a_1+a_0\equiv 0\ (mod\ 3)$ , i.e. divisible by 3.

Illustrative example: let $n=6123$ . Then

$\begin{align} 6123&=6\cdot 1000+1\cdot 100+2\cdot 10+3\\ & \equiv 6\cdot 1\ (mod\ 3)+ 1\cdot 1\ (mod\ 3)+2\cdot 1\ (mod\ 3)+3\cdot 1\ (mod\ 3) &\equiv 6+1+2+3\ (mod 3)\\ &= 12\ (mod\ 3)\\& \equiv 0\ (mod 3)\end{align}$

Thus, $6123\equiv 0 (mod\ 3)$ which implies, by definition of congruence, that $6123$ is divisible by $3$ .

The Test

A number $n$ is divisible by $4$ if the number formed by the last two digits (i.e. the 1’s and 10’s digits) of $n$ is divisible by $4$ .

Let $n=5756$ . Since the number formed by the, i.e. 56, is divisible by 4, it follows that $n=5756$ is also divisible by 4.

Because integers with more than two digits can be written as a sum of some multiple of $100$ plus a number less than $100$ . Since $4\vert 100$ , $4$ divides any multiple of $100$ , so we only need to check that $4$ divides the number formed by the last two digits.

To see this reasoning through example, let $n=2328$ . Notice that $n=2328=2300+28$ . Notice also that $4\vert 2300$ (because $2300$ is a multiple of $100$ and $4\vert 100$ ), and $4\vert 28$ . Since each of these two added numbers is divisible by 4, so is the sum; i.e. so is $n$ .

The Test

A number $n$ is divisible by $5$ if the last digit (i.e. the 1’s digit) of $n$ is divisible by $5$ (i.e. the $1$ ’s digit is a $0$ or $5$ ).

If $n=12430$ , $n$ is divisible by $5$ because the 1’s digit is $0$ which is clearly divisible by $5$ . (technically, $0$ is divisible by everything because anything times $0$ is $0$ ).

Because integers with more than one digit can be written as a sum of some multiple of $10$ plus a number less than $10$ . Since $5\vert 10$ , $5$ divides any multiple of $10$ , so we only need to check that $5$ divides the 1’s digit.

To see this reasoning through example, let $n=1375$ . Notice that $n=1375=1370+5$ . Notice also that $5\vert 1370$ (because $1370$ is a multiple of $10$ and $5\vert 10$ ), and $2\vert 5$ . Since each of these two added numbers is divisible by 5, so is the sum; i.e. so is $n$ .

The Test

A number $n$ is divisible by $6$ if and only if it is divisible by $2$ AND $3$ .

Let $n=5754$ . Then since the sum of the digits of $n$ is $21$ , and $21$ is divisible by $3$ , $n$ is also divisible by $3$ . Since the last digit of $n$ is even, $n$ is also divisible by $2$ . Hence, $n=5754$ is divisible by $6$ .

Proof of Test:

Since both $2$ and $3$ divide $6$ , if $6$ divides a number $n$ , then it follows that $2$ and $3$ must also divide this number $n$ as well.

If $6$ divides a number $n$ , then since $2$ and $3$ divide $6$ , $2$ and $3$ will divide any multiple of $6$ ; in this case $n$ .

The Test

A number $n$ is divisible by $8$ if the number formed by (i.e. the 1’s, 10’s, and 100’s digits) of $n$ is divisible by $8$ .

Let $n=5856$ . Since the number formed by the last three digits, i.e. 856, is divisible by 8, it follows that $n=5856$ is also divisible by 8.

Because integers with more than three digits can be written as a sum of some multiple of $1000$ plus a number less than $1000$ . Since $8\vert 1000$ , $8$ divides any multiple of $1000$ , so we only need to check that $8$ divides the number formed by the last three digits.

To see this reasoning through example, let $n=2128$ . Notice that $n=2128=2100+28$ . Notice also that $8\vert 2100$ (because $2100$ is a multiple of $1000$ and $8\vert 1000$ ), and $8\vert 128$ . Since each of these two added numbers is divisible by 8, so is the sum; i.e. so is $n$ .

The Test

A number $n$ is divisible by $9$ if the sum of the digits of $n$ is divisible by $9$ .

Note that if even after adding the digits the number is still too big, you can repeat the addition process until you have a number that is easy to test for divisibility by 9.

Let $n=5778$ . Then since the sum of the digits of $n$ is $27$ , and $27$ is divisible by $9$ , $n$ is also divisible by $9$ .

(See Modular Arithmetic lesson before reading this if you care)

(essentially the same reason as the test for divisibility by $3$ )

Note that $10\cong 1 (mod\ 9)$ . So, powers of $10$ such as $10,100,1000,$ etc. all have remainder $1$ when divided by $9$ .

So, if you have an integer with decimal representation $n=a_ka_{k-1}a_{k-2}\dots a_3a_2a_1a_0$ (i.e. the 1’s digit is $a_0$ the 10’s digit is $a_1$ etc.\) notice that

$a_k\cdot 10^k+a_{k-1}\cdot 10^{k-1}+\dots+a_2\cdot 100+a_1\cdot 10+a_0\equiv a_k+a_{k-1}+a_{k-2}+\dots+a_2+a_1+a_0\ (mod\ 9).$

Therefore, our number $n$ is divisible by $9$ if and only if the sum of our digits $a_k+a_{k-1}+a_{k-2}+\dots+a_2+a_1+a_0\equiv 0\ (mod\ 9)$ , i.e. divisible by 9.

Illustrative example: let $n=6345$ . Then

$\begin{align} 6345&=6\cdot 1000+3\cdot 100+4\cdot 10+5\\ & \equiv 6\cdot 1\ (mod\ 9)+ 3\cdot 1\ (mod\ 9)+4\cdot 1\ (mod\ 9)+5\cdot 1\ (mod\ 9) &\equiv 6+3+4+5\ (mod 9)\\ &= 18\ (mod\ 9)\\& \equiv 0\ (mod 9)\end{align}$

Thus, $6345\equiv 0 (mod\ 9)$ which implies, by definition of congruence, that $6345$ is divisible by $9$ .

Example 1: True or False,

$2\vert 512346$

True

$512346$ is even; i.e. the 1’s digit is divisible by $2$ .

True

The sum of the digits of $621245$ is $21$ which is divisible by $3$ .

False

$2\vert 85616$ because the number given is even, but the digits sum to $26$ and $3\not| 26$ . Need both $2$ AND $3$ to divide the number in question.

Solution

True.

Note that the last three digits give us the number $432$ which is divisible by $8$ ( $54\cdot 8=432$ ). Thus it follows that $8\vert 172432$ (because $8\vert 172000$ and $8\vert 432$ , so $8$ divides the sum).

Find an integer $c$ so that $11\cdot c= 352$ .

Note that $11\cdot 32 =352$ , and so by the definition of “divides,” there is an integer $c$ such that $11\cdot c =352$ , namely $c=32$ .

Find an integer $c$ so that $13\cdot c= -8151$ .

Note that $13\cdot -627 =-8151$ , and so by the definition of “divides,” there is an integer $c$ such that $13\cdot c =-8151$ , namely $c=-627$ .

Hint

Don’t overthink this. We are looking for an explanation as to why $17$ doesn’t (evenly) divide $300$ .

What happens when you try to divide $300$ by $17$ ? What type of number do you get (i.e. integer, ugly decimal that isn’t a whole number, etc.)? What type of number does $c$ need to be in the definition of “divides” ?

Note that $300/17=17.64705882353…$ , which is not an integer. (Stated slightly differently, 17\cdot 17.64705882352…=300\) and $17.64705882352\notin \mathbb{Z}$ ). Therefore, there is no integer $c$ such that $18\cdot c=300$ .

Previous Lesson

Back to Lesson

Next Topic