Loading web-font TeX/Math/Italic
Sample LessonSample LessonSample LessonSample LessonSample LessonSample LessonSample Lesson
Module 1: Basic Set Theory
Module 2: Modular Arithmetic, Divisibility, and the Fundamental Theorem of Arithmetic
Module 3: Functions and Relations
Module 4: Truth Tables and Symbolic Logic
Module 5: Basic Direct Proofs
Module 6: Proof Techniques Part 1: Contrapositive and Contradiction
Module 7: Sequences, Sums, and Products
Module 8: Proof Techniques Part 2: (Weak) Induction
Module 9: Recurrence Relations and Recursion
Module 10: Counting Systems (Binary, Hex, Octal, etc.)
Module 11: Combinatorics
Module 12: Graph Theory
Module 13: Review

Divisibility

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

Testing for Divisibility Tricks

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

A number n is divisible by 2 if the last digit (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.

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.

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 last two digits, 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.

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.

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.

A number n is divisible by 8 if the number formed by the last three digits (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.

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.

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.

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.

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.