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

#### Contents

## Basic Divisibility Rules

A positive integer \(N\) is divisible by

\(\large\color{green}{\boxed{\mathbf{2}}}\) if the last digit of \(N\) is 2, 4, 6, 8, or 0.

\(\large\color{green}{\boxed{\mathbf{3}}}\) if the sum of digits of \(N\) is a multiple of 3.

\(\large\color{green}{\boxed{\mathbf{4}}}\) if the last 2 digits of \(N\) are a multiple of 4.

\(\large\color{green}{\boxed{\mathbf{5}}}\) if the last digit of \(N\) is either 0 or 5.

\(\large\color{green}{\boxed{\mathbf{6}}}\) if \(N\) is divisible by both 2 and 3.

\(\large\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 \times 8 = 49\), which is a multiple of 7.)

\(\large\color{green}{\boxed{\mathbf{8}}}\) if the last 3 digits of \(N\) are a multiple of 8.

\(\large\color{green}{\boxed{\mathbf{9}}}\) if the sum of digits of \(N\) is a multiple of 9.

\(\large\color{green}{\boxed{\mathbf{10}}}\) if the last digit of \(N\) is 0.

\(\large\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.)

\(\large\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 divisiblity 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 since the last two digits ,68, are 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, \(\dfrac{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 the 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

notdivisible by \(11\).

Applying the divisibility rule of \(11,\) the difference between sum of the numbers at the odd places \((8+4+6+9 = 27 )\) and the sum of the numbers at even places \((7+5+3+9 = 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 for \( \begin{cases} 1 + 2 + a + b = 9 \\ 1 - 2 + a - b = 0, \end{cases} \) there are no integer solutions.

Solving for \( \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, so 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.

\(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 can keep applying the divisibility rules 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:

## Intermediate Divisibility Rules

A positive integer \(N\) is divisible by

\(\color{orange}{\large\boxed{\mathbf{13}}}\) if 4 times the last digit of \(N\) plus the number obtained by removing the units digit of \(N\) is a multiple of 13.

\(\color{orange}{\large\boxed{\mathbf{17}}}\) if the last digit subtracted 5 times from the remaining number (excluding the units digit) results in a number that is divisible by 17.

\(\color{orange}{\large\boxed{\mathbf{19}}}\) Double the last digit and add it to the number formed by removing the last digit in the original number. Check for divisibility by 19 in this number.

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 \(\dfrac{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) \Rightarrow 13| 4555 \). Repeating the divisibility rule, we get \(13| (4\times 5+455) \Rightarrow 13| 475 \). Repeating the rule once more, we get \(13| (4\times 5 + 47) \Rightarrow 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 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

divisibleby \(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 divisibleby \(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 divisibleby \(759284521\). \( _\square \)

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

## Divisibility Rules for Numbers Larger than 20

\(\color{red}{\large\boxed{\mathbf{23}}}\)

Add 7 times the last digit to the remaining truncated number. Repeat the step as necessary. If the result is divisible by 23, the original number is also divisible by 23

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

\(\color{red}{\large\boxed{\mathbf{29}}}\)

Add 3 times the last digit to the remaining truncated number. Repeat the step as necessary. If the result is divisible by 29, the original number is also divisible by 29

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

\(\color{red}{\large\boxed{\mathbf{31}}}\)

Subtract 3 times the last digit from remaining truncated number. Repeat the step as necessary. If the result is divisible by 31, the original number is also divisible by 31

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

\(\color{red}{\large\boxed{\mathbf{37}}}\)

Subtract 11 times the last digit from remaining truncated number. Repeat the step as necessary. If the result is divisible by 37, the original number is also divisible by 37

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

\(\color{red}{\large\boxed{\mathbf{41}}}\)

Subtract 4 times the last digit from remaining truncated number. Repeat the step as necessary. If the result is divisible by 41, the original number is also divisible by 41

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

\(\color{red}{\large\boxed{\mathbf{43}}}\)

Add 13 times the last digit to the remaining truncated number. Repeat the step as 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:: 1173+(13\(\times\)9)= 1290:: 129 is divisible by 43. 0 is ignored. So 11739 is divisible by 43

\(\color{red}{\large\boxed{\mathbf{47}}}\)

Subtract 14 times the last digit from remaining truncated number. Repeat the step as 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:: 4502 – (14\(\times\)6) =4418. Since 441 – (14\(\times\)8) =329, which is 7 times 47. Hence 45026 is divisible by 47

## Proving Divisibility Rules

## 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 = (10 - (-1) ) \left( 10^{n-1} + 10^{n-2}(-1) + \ldots + (-1)^{n-1} \right)\]

is always a multiple of \(11.\)

Hence, if \( N = 10^k a_k + 10^{k-1} a_{k-1} + \ldots + 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]\\ & \quad + (-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\)

## Finding Divisibility Rules

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

\[\overline { abc } \equiv 0\quad \left( \text{mod 13} \right) \\ 100a+10b+c\equiv 0\quad \left( \text{mod 13} \right) \\ 10\left( 10a+b \right) +c\equiv 0\quad \left( \text{13} \right) \\ 10\overline { ab } +c\equiv 0\quad \left( \text{13} \right) \]

Now that we have separated the last digit from the number, we have to find a way using which, the coefficient of \(\overline { ab }\) is 1. In other words, we have to find an integer \(n\) such that \(10n\equiv 1\quad \left( \text{mod 13} \right) \). 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.

\[10\overline { ab } +c\equiv 0\quad \left( \text{mod 13} \right) \\ 40\overline { ab } +4c\equiv 0\quad \left( \text{mod 13} \right) \\ \overline { ab } +4c\equiv 0\quad \left( \text{13} \right) \]

Aha! We have found out that if \(\overline { abc } \equiv 0\quad \left( \text{mod 13} \right)\) then \(\overline { ab } +4c\equiv 0\quad \left( \text{mod 13} \right) \). 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

\[\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 }{ x }_{ 1 } } \equiv 0\quad \left( \text{mod 13} \right) \\ 10\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +{ x }_{ 1 }\equiv 0\quad \left( \text{mod 13} \right) \\ 40\overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +4{ x }_{ 1 }\equiv 0\quad \left( \text{mod 13} \right) \\ \overline { { x }_{ n }{ x }_{ n-1 }{ x }_{ n-2 }\dots { x }_{ 2 } } +4{ x }_{ 1 }\equiv 0\quad \left( \text{mod 13} \right) \]

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.

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?

## See Also

**Cite as:**Divisiblity Rules (2,3,5,7,11,13,17,19,...).

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/divisibility-rules/