Divisibility Rules (2,3,5,7,11,13,17,19,...)

A divisibility rule is a heuristic for determining whether a positive integer can be evenly divided by another (i.e. there is no remainder left over). For example, determining if a number is even is as simple as checking to see if its last digit is 2, 4, 6, 8 or 0. Multiple divisibility rules applied to the same number in this way can help quickly determine its prime factorization without having to guess at its prime factors.

A positive integer \(N\) is divisible by

• \(\color{green}{\boxed{\mathbf{2}}}\) if the last digit of \(N\) is 2, 4, 6, 8, or 0;
• \(\color{green}{\boxed{\mathbf{3}}}\) if the sum of digits of \(N\) is a multiple of 3;
• \(\color{green}{\boxed{\mathbf{4}}}\) if the last 2 digits of \(N\) are a multiple of 4;
• \(\color{green}{\boxed{\mathbf{5}}}\) if the last digit of \(N\) is either 0 or 5;
• \(\color{green}{\boxed{\mathbf{6}}}\) if \(N\) is divisible by both 2 and 3;
• \(\color{green}{\boxed{\mathbf{7}}}\) if subtracting twice the last digit of \(N\) from the remaining digits gives a multiple of 7 (e.g. 658 is divisible by 7 because 65 - 2 x 8 = 49, which is a multiple of 7);
• \(\color{green}{\boxed{\mathbf{8}}}\) if the last 3 digits of \(N\) are a multiple of 8;
• \(\color{green}{\boxed{\mathbf{9}}}\) if the sum of digits of \(N\) is a multiple of 9;
• \(\color{green}{\boxed{\mathbf{10}}}\) if the last digit of \(N\) is 0;
• \(\color{green}{\boxed{\mathbf{11}}}\) if the difference of the alternating sum of digits of \(N\) is a multiple of 11 (e.g. 2343 is divisible by 11 because 2 - 3 + 4 - 3 = 0, which is a multiple of 11);
• \(\color{green}{\boxed{\mathbf{12}}}\) if \(N\) is divisible by both 3 and 4.

Here are some example questions that can be solved using some of the divisibility rules above.

Without performing actual division, show that the number below is an integer:

\[\dfrac{1,481,481,468}{12}.\]

---

From the divisibility rules, we know that a number is divisible by 12 if it is divisible by both 3 and 4. Therefore, we just need to check that 1,481,481,468 is divisible by 3 and 4.

Applying the divisibility test for 3, we get that \(1+4+8+1+4+8+1+4+6+8=45,\) which is divisible by 3. Hence 1,481,481,468 is divisible by 3.

Applying the divisibility test for 4, we get that the last two digits, 68, is divisible by 4. Hence 1,481,481,468 is also divisible by 4.

Now, since we know that 1,481,481,468 is divisible by both 3 and 4, it is divisible by 12. Therefore, \(\frac{1,481,481,468}{12}\) will be an integer. \(_\square\)

Find all the possible values of \( a\) such that the number \( \overline{98a6}\) is a multiple of \(3.\)

---

From the rules of divisibility, the number \( \overline{98a6}\) is a multiple of \(3\) if and only if the sum of its digits \( 9 + 8 + a + 6 = 23+a\) is a multiple of \(3.\) Since \( 0 \leq a \leq 9\), this implies that \( a = 1, 4, 7\) are all the possible values. \(_\square\)

Without performing division, explain why the number \(987654321\) is a multiple of \(9\).

---

By the rule of divisibility of \(9,\) since \(9+8+7+6+5+4+3+2+1 = 45 \) is a multiple of \(9,\) \(987654321\) is a multiple of \(9. \ _\square\)

Without performing actual division, show that \(87456399\) is not divisible by \(11\).

---

Applying the divisibility rule of \(11,\) the difference between the sum of digits at the odd places \((8+4+6+9 = 27 )\) and the sum of digits at even places \((7+5+3+9 = 24)\) is \(27-24=3,\) which is not divisible by \(11\). Hence \(87456399\) is not divisible by \(11\). \(_\square\)

For what values of \(a\) and \(b\) is \( \overline{12ab} \) a multiple of \(99?\)

---

Since \( 99 = 9 \times 11 \), the number must be a multiple of \(9\) and \(11.\)

The divisibility rule of \(9\) tells us that \( 1 + 2 + a + b \) is a multiple of \(9.\) Since it is a number from \(3\) to \(21,\) it must be either \(9\) or \(18.\)

Now, the divisibility rule of \(11\) tells us that \( 1 - 2 + a - b \) is a multiple of \(11.\) Since it is a number from \(-10\) to \(8,\) it must be \(0.\)

Solving \( \begin{cases} 1 + 2 + a + b = 9 \\ 1 - 2 + a - b = 0, \end{cases} \) there are no integer solutions.

Solving \( \begin{cases} 1 + 2 + a + b = 18 \\ 1 - 2 + a - b = 0, \end{cases} \) we get \( a = 8, b = 7 \).

Hence, the only solution is \( 1287 \) with \( a = 8\) and \(b = 7. \) \(_\square\)

Is \(65973390\) divisible by \(210?\)

---

We do not know the divisibility rule of 210. However, we can easily see that \(210=2\times 3\times 5\times7\), so if 65973390 is divisible by 2, 3, 5, 7, then it is divisible by 210.

• Since the last digit of 65973390 is 0, it is divisible by 2.
• Since \(6+5+9+7+3+3+9+0=42\), which is divisible by 3, it follows that 65973390 is divisible by 3.
• Since the last digit of 65973390 is 0, hence it is divisible by 5.
• To check divisibility by 7, as the initial step, we calculate \(6597339-2(0)=6597339\). However, this number is still a little too big for us to tell whether it's divisible by 7. In such cases, we keep applying the divisibility rule again and again until we have a small enough number to work with: \[\begin{align}659733-2(9)&=659715\\65971-2(5)&=65961\\6596-2(1)&=6594\\659-2(4)&=651\\65-2(1)&=63.\end{align}\] Now we can see that we are left with \(63,\) which we can easily identify as a multiple of 7. Hence 65973390 is a multiple of 7 also.

Since 65973390 is divisible by all of 2, 3, 5, 7, it is divisible by \(2\times3\times5\times7=210. \ _\square\)

Try some problems for yourself to see if you understand this topic:

A positive integer \(N\) is divisible by

• \(\color{orange}{\boxed{\mathbf{13}}}\) if 4 times the units digit of \(N\) plus the number obtained by removing the units digit of \(N\) is a multiple of 13;
• \(\color{orange}{\boxed{\mathbf{17}}}\) if the units digit subtracted 5 times from the remaining number (excluding the units digit) results in a number that is divisible by 17;
• \(\color{orange}{\boxed{\mathbf{19}}}\) if doubling the units digit and adding it to the number formed by removing the units digit in the original number is divisible by 19.

You may use these rules repeatedly until you can tell if a number is divisible by another number or not.

It is also useful to note that the notation \(x | y \) is used to say \(x\) divides \(y\), i.e. the fraction \(\frac{y}{x}\) gives an integer. For example, \(\color{green}{ 3| 6 }\) is true, but \(\color{red}{ 2| 7}\) is false.

Is \(45238\) divisible by \(13?\)

---

From the rules of divisibility, the number \(45238\) is a multiple of \(13\) if and only if \(13| (4\times 8+4523) \implies 13| 4555 \). Repeating the divisibility rule, we get \(13| (4\times 5+455) \implies 13| 475 \). Repeating the rule once more, we get \(13| (4\times 5 + 47) \implies 13| 67 \), which is clearly \(\color{red}{\text{false}}\). Therefore, \(45238\) is not divisible by \(13\). \(_\square\)

Is \(2853598728\) divisible by \(24?\)

---

\(24\) is a composite number, so we will have to deal with it in a slightly different way. We can write \(24\) as \( 3 \times 8 \). If a number is divisible by both \(3\) and \(8\), then the number is also divisible by \(24\). We choose \(3\) and \(8\) because they are coprime, and also because we know the divisibility rules for \(3\) and \(8\).

Let's test if \(2853598728\) is divisible by \(8\). The last three digits of the number are \(728\) which is divisible by \(8\), so \(2853598728\) is also divisible by \(8\). Now let's see if \(2853598728\) is divisible by \(3\). The sum of digits of \(2853598728\) is \(57\). Since \(57\) is divisible by \(3\), \(2853598728\) is also divisible by \(3\). Since \(2853598728\) is divisible by both \(3\) and \(8\), we can conclude that \(2853598728\) is divisible by \(24\). \(_\square \)

Is \(365226929\) divisible by \(2976?\)

---

We do not know the divisibility rule for \(2976\). However, we know that since \(2976\) is even, any integral multiple of \(2976\) will be even. However, \(365226929\) is not even, so \(365226929\) is not divisible by \(2976\). \( _\square \)

Is \(25729875\) divisible by \(759284521?\)

---

Since \( 0 < 25729875 < 759284521\), we see that it is between two consecutive multiples of \(759284521\). Hence \(25729875\) is not a multiple of \(759284521\), and \(25729875\) is not divisible by \(759284521\). \( _\square \)

Try some problems for yourself to see if you understand this topic:

\(\color{red}{\boxed{\mathbf{23}}}\) Add 7 times the last digit to the remaining truncated number. Repeat the step if necessary. If the result is divisible by 23, the original number is also divisible by 23.

• Check for 53935: \(5393+7\times 5 = 5428 \implies 542+7\times 8= 598 \implies 59+ 7\times 8=115,\) which is 5 times 23. Hence 53935 is divisible by 23.

\(\color{red}{\boxed{\mathbf{29}}}\) Add 3 times the last digit to the remaining truncated number. Repeat the step if necessary. If the result is divisible by 29, the original number is also divisible by 29.

• Check for 12528: \(1252+3\times 8= 1276 \implies 127+3\times 6= 145\implies 14+ 3\times 5=29,\) which is divisible by 29. So 12528 is divisible by 29.

\(\color{red}{\boxed{\mathbf{31}}}\) Subtract 3 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 31, the original number is also divisible by 31.

• Check for 49507: \(4950-3\times 7=4929 \implies 492-3\times 9= 465\implies 46-3\times 5=31.\) Hence 49507 is divisible by 31.

\(\color{red}{\boxed{\mathbf{37}}}\) Subtract 11 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 37, the original number is also divisible by 37.

• Check for 11026: We have \(1102 – 11\times 6 =1036.\) Since \(103 – 11\times 6 =37\) is divisible by 37, 11026 is divisible by 37.

\(\color{red}{\boxed{\mathbf{41}}}\) Subtract 4 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 41, the original number is also divisible by 41.

• Check for 14145: We have \(1414 – 4\times 5 =1394.\) Since \(139 – 4\times 4 =123\) is divisible by 41, 14145 is divisible by 41.

\(\color{red}{\boxed{\mathbf{43}}}\) Add 13 times the last digit to the remaining truncated number. Repeat the step if necessary. If the result is divisible by 43, the original number is also divisible by 43. (This process becomes difficult for most of the people because of multiplication with 13.)

• Check for 11739: We have \(1173+13\times 9= 1290.\) Since 129 is divisible by 43, the 0 can be ignored. So, 11739 is divisible by 43.

\(\color{red}{\boxed{\mathbf{47}}}\) Subtract 14 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 47, the original number is also divisible by 47. (This too is difficult to operate for people who are not comfortable with table of 14.)

• Check for 45026: We have \(4502 – 14\times 6 =4418.\) Since \(441 – 14 \times 8 =329,\) which is 7 times 47, 45026 is divisible by 47.

Prove that when a number is divisible by \(7,\) the result when subtracting twice the last digit from the number formed by the remaining digits is a multiple of \(7.\)

---

Let the number be \( N= 10a + b\), where \( b\) is the last digit of \(N\) and \(a\) is the number formed by the remaining digits.

Now we have to prove that if \(a-2b\) is divisible by \(7,\) then \(N=10a+b\) must be also divisible by \(7.\)

Let \(a-2b=7k,\) where \(k\) is an integer, and multiply this equation by \(10\) and add \(b\) to both sides. Then you'll get

\[10a-20b+b=70k+b.\]

Now move \(-20b\) to the right, and you'll get

\[10a+b=N=70k+21b,\]

which is a multiple of \(7.\) \(_\square\)

Prove that when a number is divisible by \(8,\) the last \(3\) digits are a multiple of \(8.\)

---

Let the number be \( N= 1000M + 100a + 10b + c\), where \( a, b, c\) are digits and \( M\) is a non-negative integer.

Clearly, \( 1000M\) is a multiple of \(8,\) since \( 8 \mid 2^3 \cdot 5^3\). Hence, \( N\) is a multiple of \(8\) if and only if \( 100a + 10b + c\) is a multiple of \(8.\) \(_\square\)

Prove that when a number is divisible by \(11,\) the alternating sum of digits is a multiple of \(11.\)

---

From factorization , we know that

\[ 10^n - (-1)^n = \big(10 - (-1) \big) \left( 10^{n-1} + 10^{n-2}(-1) + \cdots + (-1)^{n-1} \right)\]

is always a multiple of \(11.\)

Hence, if \( N = 10^k a_k + 10^{k-1} a_{k-1} + \cdots + 10 a_1 + a_0\), then

\[ \begin{aligned} N = &\left[\left(10^k - (-1)^k\right) a_k + \left( 10^{k-1} - (-1)^{k-1}\right) a_{k-1} + \cdots + (10+1)a_1 + (1-1)a_0 \right]\\\\ & \hspace{4cm}+ (-1)^k a_k + (-1)^{k-1}a_{k-1} + \cdots + (-1)^1 a_1 + (-1)^0 a_0. \end{aligned} \]

Since the terms in the square brackets consist of multiples of \(11,\) it follows that \( N\) is a multiple of \(11\) if and only if the alternating sum is a multiple of \(11.\) \( _ \square\)

Although finding clever divisibility tricks requires a bit of ingenuity, finding general divisibility tests is not hard. In this section, we are only going to focus on finding divisibility tests for primes as once we know test for primes, we can decompose any composite number into primes and test for divisibility.

Let's start with an example.

Find the divisibility test for 13.

---

Let's first find a test for small 3-digit numbers first and then find a general test. We'll be finding tests which involves separation of last digit. These tests will be similar to the tests of 19, 23, 29, etc.

Let \(\overline { abc }\) be any number such that \(\overline { abc } =100a+10b+c\). Now assume that \(\overline { abc }\) is divisible by 13. Then

\[\begin{align} \overline { abc } &\equiv 0 \pmod{13}\\ 100a+10b+c &\equiv 0 \pmod{13}\\ 10\left( 10a+b \right) +c &\equiv 0 \pmod{13}\\ 10\overline { ab } +c &\equiv 0 \pmod{13}. \end{align}\]

Now that we have separated the last digit from the number, we have to find a way to use it: make the coefficient of \(\overline { ab }\) 1. In other words, we have to find an integer \(n\) such that \(10n\equiv 1 \bmod{13} \). It can be observed that the smallest \(n\) which satisfies this property is 4. Now we can multiply the original equation by 4 and simplify it:

\[\begin{align} 10\overline { ab } +c &\equiv 0 \pmod{13} \\ 40\overline { ab } +4c &\equiv 0 \pmod{13}\\ \overline { ab } +4c &\equiv 0 \pmod{13}. \end{align}\]

Aha! We have found out that if \(\overline { abc } \equiv 0 \bmod{13},\) then \(\overline { ab } +4c\equiv 0 \bmod{13}\). In other words, to check if a 3-digit number is divisible by 13, we can just remove the last digit, multiply it by 4, and then add it to the rest of the two digits.

Now that we have found out the test for 3-digit numbers, let's find out a general divisibility test. Let \(\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 }{ x }_{ 1 } } \) be any \(n\) digit number. Then

\[\begin{align} \overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 }{ x }_{ 1 } } &\equiv 0 \pmod{13}\\ 10\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +{ x }_{ 1 } &\equiv 0 \pmod{13}\\ 40\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +4{ x }_{ 1 } &\equiv 0 \pmod{13}\\ \overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +4{ x }_{ 1 } &\equiv 0 \pmod{13}. \end{align}\]

Hence, a number is a multiple of 13 if we add 4 times the last digit to the rest of the number and the resulting number is still divisible by 13. \(_\square\)

This process can be repeated by any arbitrary prime number to find its divisibility test. Now can you find the divisibility tests for 17, 19, 23 and 29 on your own?

Try some problems for yourself to see if you understand this topic:

• Proof of Divisibility Rules
• Prime Numbers
• Prime Factorization
• Remainder