Divisibility

Divisibility Tests

Tricks and shortcuts for testing divisibility of numbers by various integers.

Divisibility by 2

We know that if the last digit in a number is divisible by 2, the entire number is divisible by 2. This stems from the fact that 2 divides 10 perfectly. Thus, every number can be split into two parts: the ones column, and the tens-and-higher column. The tens-and-higher column are all multiples of 10, which are divisible by 2, so those will "disappear" when we chunk out numbers that are divisible by 2. If we can ignore any number in the tens, hundreds, thousands, etc. columns, all that matters is that first part: the number in the ones column.

Example: 416

416 = 41 * 10 + 6

We know 2 will divide 41 * 10 perfectly, because 2 divides 10. Thus, the only question remaining is whether 2 divides the last digit, 6, which it does. So, 2 divides 416.

Example: 1111222233334

1111222233334 = 111122223333*10 + 4

We know 2 will divide 111122223333*10 perfectly, because 2 divides 10. We also know 2 will divide the digit in the ones column, so 2 divides 1111222233334 evenly.

Divisibility by 3

We know that if the digit sum of a number is divisible by 3, the number itself is divisible by 3. If the sum of the digits forms a large number, its digits can be added together in a like fashion.

Example: 15,230,127

15,230,127 => 1 + 5 + 2 + 3 + 0 + 1 + 2 + 7 = 21 
21 => 2 + 1 => 3

The sum of the digits is 3, therefore 3 divides 15,230,127.

Divisibility by 4

If the last two digits of a number are divisible by 4, the entire number is divisible by 4. The mechanism for this is similar to the mechanism for the divisibility tests for 2 and for 5. Because 4 divides 100 perfectly, any number can be split into its hundreds and greater component, and its tens and ones digits. 4 will evenly divide the hundreds and greater component, since it perfectly divides 100. The only remaining thing to determine is whether 4 divides the last 2 digits.

Divisibility by 5

If a number ends in 0 or 5, it is divisible by 5. This is due to the fact that 5 divides 10 perfectly, like 2, so any number can be split into its ones value (which 5 may or may not divide) and everything else (which 5 will divide).

Divisibility by 6

This actually bootstraps from the divisibility test by 7, explained more in detail below. It uses a similar approach to decompose base 10 into base 6 and base 4, instead of base 7 and base 3.

Suppose we are checking whether a number N is divisible by 6.

Decompose N into its digits as:

N = edcba 
N = a + 10 b + 100 c + 1000 d + 10000 e
N = a + 10 b + 10^2 c + 10^3 d + 10^4 e

Ultimately we are trying to determine if N is equal to 0 mod 6, so write this as:

N = a + 10 b + 10^2 c + 10^3 d + 10^4 e (mod 6)

Now we can write 10 as 10 = (6 + 4), and N becomes

N = a + ( 6 + 4 ) b + (6 + 4)^2 c + (6 + 4)^3 d + (6 + 4)^4 e (mod 6)

If we expand the various powers of (6+4), we will always have a sequence of terms divisible by 6, plus a power of 4. The coefficients can then be reduced mod 6, so all terms divisible by 6 will disappear:

(6 + 4) b = 4 b (mod 6)
(6 + 4)^2 c = (6^2 + 2*4*6 + 4^2) c = 4^2 c (mod 6)
(6 + 4)^3 d = (6^3 + 3*6^2*4 + 3*6*4^2 + 4^3) d = 4^3 d (mod 6)
(6 + 4)^4 e = (6^4 + 4*6^3*4 + 6*6^2*4^2 + 4*6*4^3 + 4^4) e = 4^4 e (mod 6)

Thus, we can reduce the polynomial expression for N by chunking into parts divisible by 6 and parts not divisible by 6:

N = a + 10 b + 10^2 c + 10^3 d + 10^4 e
N = a + (6 + 4) b + (6+4)^2 c + (6+4)^3 d + (6+4)^4 e
N = a + 4 b + 4^2 c + 4^3 d + 4^4 e

The last step in implementing this trick is to rewrite the formula above in a recursive fashion:

N = a + 4( b + 4( c + 4( d + 4( e ) ) ) ) 

Now this can be translated into a rule to check for divisibility by 6:

Starting with a number N = edcba, this procedure will check whether it is divisible by 6. Start with the left-most digit of a number, say e. Multiply by 4, and add the next digit d. Multiply the result by 4, and add the next digit c. Multiply the result by 4, and add the next digit b. Multiply the result by 4, and add the next digit a. If the result is divisible by 6, then the entire number N is divisible by 6.

To simply the above procedure, you can reduce each result modulo 4 (although this is entirely optional - the result will be divisible by 6 whether you reduce modulo 4 at each step or not.)

Example: 18

18:
8 + 4(1) = 12

(Here, the leftmost digit goes on the inside because that's the digit we start with.)

Therefore, because the result 12 is divisible by 6, 18 is divisible by 6.

Example: 858 (which is 6 * 143)

858:
8 + 4( 5 + 4( 8 ) ) = 8 + 4( 5 + 32 ) = 8 + 4 ( 37 ) = 8 + 148 = 156

Therefore, 858 is divisible by 6, because 156 is divisible by 6. This can be done in an easier way by reducing mod 4 along the way:

8 + 4( 5 + 4 ( 8 ) ) = 8 + 4 ( 5 + 32 ) = 8 + 4 ( 5 + 2 ) = 8 + 4 ( 7 ) = 8 + 4 ( 1 ) = 12

Therefore, 858 is divisible by 6, because the result 12 is divisible by 6.

Example: 216 (which is 6^3)

216:
6 + 4( 1 + 4( 2 ) ) = 6 + 4 ( 1 + 8 ) = 6 + 4(9) = 6 + 36 = 42

Because 42 is divisible by 6, the original number 216 is divisible by 6.

Example: 720 (which is 6!)

720:
0 + 4( 2 + 4( 7 ) ) = 4( 2 + 28 ) = 4 * 30

which is definitely divisible by 6. Therefore, 720 is divisible by 6.

Divisibility by 7

The Russian people like the number 7... Folk songs and proverbs:

• Measure cloth seven times before you cut it
• Seven misfortunes, one reckoning
• One plows, seven come along with spoons
• A baby had seven nurses, but lost his eye

We know two kinds of tests of divisibility by 7, in conjunction with other numbers (3/7/19 and 7/11/13).

Test A

Here is another test:

Start with the first digit on the left. (first = left)

Multiply the first digit on the left by 3. Add the second digit.

Multiply the result by 3. Add the third digit.

Multiply the result by 3. Add the fourth digit.

Repeat, until you get to the ones column (right-most digit).

When you get to the ones column, just add the ones column. (No multiplication by 3.)

If the last result is divisible by 7, the entire number is divisible by 7.

To simplify your calculations, reduce each multiplication result modulo 7. (For example, 8 = 1 (mod 7), and 15 = 1 (mod 7), and etc.)

Example: 48,916

48,916

Multiply by 3:
4 * 3 = 12 = 5 mod 7
Add next digit:
5 + 8 = 13 = 6 mod 7

Multiply by 3:
6 * 3 = 18 = 4 mod 7
Add next digit:
4 + 9 = 13 = 6 mod 7

6 * 3 = 18 mod 7 = 4 mod 7
4 + 1 = 5

5 * 3 = 15 mod 7 = 1 mod 7
1 + 6 = 7

The last number is 7, therefore 48,916 is divisible by 7.

Test A Proof

To prove the validity of the test, we can take a given number N = edcba and represent it as follows:

N = a + 10 b + (10^2) c + (10^3) d + ...

What we want to do is determine if this number is divisible by 7. If we can remove known factors of 7 from this representation, we can reduce the problem - this is similar in principle to the divisibility check with 2 and 4, where the 10s or 100s place can be removed because it is a known factor of 2 or 4.

Again, the principle of modular arithmetic is showing up; if we want to check whether 15 is divisible by 7, we can say, "break 15 into a portion that is known to be divisible by 7, that is, 14, and the remainder, that is, 1". Decomposing 15 = 14 + 1, we can then say that 14 = 0 mod 7, and drop the 14 portion, and the divisibility check becomes "does 7 divide 1 perfectly?" which it does not. Therefore 15 does not divide 7.

Using this principle, we decompose N into parts reducible mod 7, and the remainder:

N = a + 10 b + 10^2 c + 10^3 d + ...
= a + (7 + 3) b + (7 + 3)^2 c + (7 + 3)^3 d + ...
= a + (7 + 3) b + (7 + 3)^2 c + (7 + 3)^3 d + ... (mod 7)

Now break this into parts divisible by 7, and the rest. We can use the formulas for the binomial expansion of (a + b)^k to show that in the expansion of (a+b)^k, every term in the resulting expression will be divisible by a except for b^k. This means that every term in (7+3)^k will be divisible by 7 except 3^k, and so the expression (7+3)^k reduces to 3^k mod 7. For example, (7+3)^2 mod 7 = 7^2 + 7*3 + 3^2 mod 7 = 3^2 mod 7, which is easier to reduce.

Thus, when factors of 7 are removed in this way, N becomes:

N = a + 3 b + 3^2 c + 3^3 d + ... (mod 7)

When this is written recursively, it becomes obvious how this translates to the procedure described above:

N = a + 3(b + 3(c + 3(d + 3(...

Test B

This test is similar to Test A, except for the last step.

Start with the first digit on the right. (first = right)

Multiply this digit by 5, and add the next digit to the left. Reduce this mod 7.

Multiply this result by 5, and add the next digit to the left. Reduce this mod 7.

Repeat the procedure.

When you reach the last column, add the digit to your result and stop.

If the last result is divisible by 7, the entire number is divisible by 7.

To simplify your calculations, reduce each multiplication result modulo 7. (For example, 8 = 1 (mod 7), and 15 = 1 (mod 7), and etc.)

Example: 26,040

26,040

Start with first digit on right:
0
Multiply by 5 and add the next digit to the left:
0*5 + 4 = 4 mod 7
Multiply by 5 and add the next digit to the left:
4*5 + 0 = 20 mod 7 = 6 mod 7
Multiply by 5 and add the next digit to the left:
6*5 + 6 = 36 mod 7 = 1 mod 7
Multiply by 5 and add the next digit to the left:
1*5 + 2 = 7 mod 7 = 0 mod 7

The last number is 7, and is therefore divisible by 7, so our original number 26,040 is also divisible by 7.

Proof of Test B

The proof of Test A can be used to prove Test B as well. Starting from the representation of N = edcba with the factors of 7 already removed,

N = a + 3 b + 3^2 c + 3^3 d + ...

We can divide this entire number by 3^n, where n is the number of digits, and obtain (for example, for n=4):

N = (1/3^4) a + (1/3^3) b + (1/3^2) c + (1/3) d + e (mod 7)

we can compute 1/3 mod 7, which becomes 5 mod 7, making this expression:

N = 5^4 a + 5^3 b + 5^2 c + 5 d + e

which, when expressed recursively, translates into the Test B procedure:

N = e + 5(d + 5(c + 5( b + 5( a + 0 ) ) ) ) )

Divisibility by 9

We know that if the digit sum of a number is divisible by 9, the number itself is divisible by 9.

Divisibility by 11

To test for divisibility by 11:

• Add the numbers in the even positions (second, fourth, and so on).
• Add the digits in the odd positions (first, third, and so on)
• If the difference between the sums is 0 or a multiple of 11, the number is divisible by 11.
• Otherwise, it is not a multiple of 11.

Example: 181,182,375

181,182,375 => (1+1+8+3+5) - (8+1+2+7) = 18 - 18 = 0

Therefore, 181,182,375 is divisible by 11.

Proof/Explanation

This introduces the term modulus - similar to remainder. 18 has a remainder of 7 when divided by 11, and 18 = 7 mod 11.

The digits 0, 1, 2, 3, ..., 9 are, of course, 0, 1, 2, ..., 9 mod 11

0, 10, 20, ..., 90 are, by actual division, 0, 10, 9, ..., 2 mod 11 = 0, -1, -2, ..., -9 mod 11

0, 100, 200, ... 900 are again 0, 1, 2, ..., 9 mod 11 and so on

The sum of two given numbers has the same modulus as the sum of the moduli of the numbers. For a given number N:

N = a + 10 b + 100 c + 1000 d + ...

Now expressing that mod 11:

N mod 11 = a mod 11 + 10 b mod 11 + 100 c mod 11 + 1000 d mod 11 + ... = a mod 11 - b mod 11 + c mod 11 - d mod 11 + ... = a mod 11 + c mod 11 + ... - ( b mod 11 + d mod 11 + ... )

Since a, b, c, d, are the digits of N, starting from right to left, the test must be correct.

Divisibility by 13

Here is a test to see if a number N is divisible by 13.

Start with the left-most digit, and multiply it by negative 3.

Add the next digit to the right.

Multiply it by negative 3.

Add the next digit to the right.

Etc.

Reduce modulo 13 after each step.

If the resulting number is 0 or is a multiple of 13, then the original number N is divisible by 13.

This can be expressed in a formula for a number N = edcba as:

a - 3( b - 3( c - 3( d - 3( e ) ) ) ) 

If this number is 0 or is divisible by 13, then the original number N = edcba is divisible by 13.

Example: 130

130:
0 - 3( 3 - 3( 1 ) ) = -3( 3 - 3 ) = 0

Therefore, 130 is divisible by 13.

Example: 325 (which is 13 * 25)

325:
5 - 3( 2 - 3( 3 ) ) = 5 - 3( 2 - 9) = 5 - 3(-7) = 21+5 = 26

Therefore, 325 is divisible by 13.

Proof

Start by expressing a multiple-digit number N=edcba in polynomial form:

N = a + 10 b + 100 c + 1000 d + 10000 e
N = a + 10 b + 10^2 c + 10^3 d + 10^4 e

Recall that we are trying to determine if this is equal to 0 mod 13, so we can write this number as mod 13:

N = a + 10 b + 10^2 c + 10^3 d + 10^4 e (mod 13)

Next, 10 can be decomposed as 10 = 13 - 3, and the number N becomes:

N = a + (13 - 3) b + (13 - 3)^2 c + (13 - 3)^3 d + (13 - 3)^4 e (mod 13)

Now the components that are divisible by 13 can be eliminated mod 13, and because of the nature of the binomial expansion (13 - 3)^k, a factor of 13 will show up in every term except for the last 3^k term, so this can be reduced mod 13 to (careful of the signs):

N = a - 3 b + 3^2 c - 3^3 d + 3^4 e

Which, when expressed as a nested function, becomes:

N = a - 3( b - 3( c - 3( d - 3( e ) ) ) )

Now this yields a formula to check for divisibility by 13:

Starting with the left-most digit:

1. Multiply by -3

2. Add the next digit

3. Repeat step 1, then step 2, on the result

Reduce mod 13 as you go. If the final result is 0 or divisible by 13, then the entire number is divisible by 13.

Example

Quick example: 325

5 - 3( 2 - 3( 3 ) ) = 5 - 3( 2 - 9 ) = 5 - 3( -7 ) = 21 + 5 = 26

Bingo! 325 is divisible by 13. In fact it is 13*25.

Longer example on a larger number:

$13\times 10!=47,174,400$

Number: 47174400

Start with left-most digit (0):
0
Multiply by -3 and add the next digit (0):
-3 * 0 + (0) => 0
Multiply result by -3 and add the next digit (4):
-3 * 0 + (4) => 4
Multiply result by -3 and add the next digit (4):
-3 * 4 + (4) => -8
Multiply result by -3 and add the next digit (7):
(and using 31 mod 13 = 5 mod 13):
-3 * -8 + (7) => 31 => 5 
Multiply result by -3 and add the next digit (1):
(and using -14 mod 13 = -1 mod 13):
-3 * 5 + (1) => -14 => -1
Multiply result by -3 and add the next digit (7):
-3 * -1 + (7) => 10
Multiply result by -3 and add the next digit (4):
-3 * 10 + (4) => -26

Finally, because -26 mod 13 = 0 mod 13,
we can confirm that 41714400 is divisible by 13.
(It is in fact 13 x 3628800 or 13 x 10!)

Divisibility by 37

Just to go out on a limb, I wanted to see if I could devise a divisibility test for 37. How can we test a very large number to see if it is divisible by 37, using only its digits?

This one required a little more thinking and trial-and-error, but resulted in a more general procedure for devising divisibility tests.

Let's start with the test for 37:

For a multi-digit number N = edcba, it can be determined if the number is divisible by 37 using the following technique:

Starting with the right-most digit:

1. Multiply by -11

2. Add the next digit over

3. Repeat step 1, then step 2, on the result

Continue until all digits have been added. Reduce results modulo 37 as you go. If the result of this calculation is 0 or is divisible by 37, then the original number N is divisible by 37.

Example: 3330 (which is 37*90)

3330:

(Starting with right-most digit)

Multiply by -11:
-11*(0) = 0
Add next digit over:
3 + 0 = 3
Multiply by -11:
-11*3 = -33
Add next digit over:
- 33 + 3 = -30
Multiply by -11:
330 
Add next digit over:
330 + 3 = 333

Because 333 is divisible by 37 (333 = 37*9), the number 3330 is also divisible by 37.

Proof

Write a number N = edcba as:

N = a + 10 b + 10^2 c + 10^3 d + 10^4 e

Now, with prior divisibility tests (6, 7, 11), our approach was to decompose 10. Here were the different decompositions we used:

6: 10 = 6 + 4
7: 10 = 7 + 3
7: 1/3 = 5 mod 7
11: 11 = -1 mod 10
13: 13 = 13 - 3

The most obvious way to decompose 10 so that we can chunk out terms divisible by 37 is to say:

10 = 37 - 27

and write N as

N = a + (37 - 27) b + (37 - 27)^2 c + ...

But this would be counterproductive, as we're then left with the much more cumbersome:

N = a - 27 b + 27^2 c - 27^3 d + 27^4 e (mod 37)

Yikes. Let's try, instead, rewriting N in terms of 1/10:

N = a + 10 b + 10^2 c + 10^3 d + 10^4 e (mod 37)
N/10^4 = a/10^4 + b/10^3 + c / 10^2 + d / 10 + e (mod 37)

The idea here is, if N is divisible by 37, then N equals 0 mod 37, so N/10^4 also equals 0 mod 37.

Now, if we compute the value of 1/10 mod 37, we find that 1/10 = 26 (mod 37) and therefore it doesn't make it much simpler than -27.

However, if we write 26 as -11, we can formula the following expression:

(-11)^4 a + (-11)^3 b + (-11)^2 c + (-11) d + e
e - 11( d - 11( c - 11( b - 11( a ) ) ) )

If the result of this calculation is 0 or divisible by 37, then the original number N is divisible by 13.

Devising Divisibility Tests

Divisibility tests for factors that are powers of 10

An easy (but quick-to-dead-end) shortcut for divisibility checks is if you can factor 1,000, 10,000, or 100,000, or any other power of 10 OUT OF your number m.

Then, you can just toss out the left-most X digits and just keep the last Y digits.

For example, the divisibility test for 40 is the same as the divisibility test for 4, on the target divided by 10. ("Does 40 divide 200" is the same question as "does 4 divide 20".)

tests for small-ish numbers

Composing this type of divisibility test gets more difficult the further away from 10 you get, but is still feasible with e.g. 37.

To devise a divisibility test (to determine if a large number N is divisible by a smaller number m) in the style of the tests for 6, 7, 11, 13, and 37, we can express a number N = edcba in terms of its digits as a polynomial,

N = a + 10b + 10^2 c + 10^3 d + 10^4 e (mod m)

Now the trick is to decompose 10 into a sum of two numbers: one that is a known factor of m, and can be reduced mod m to a smaller number - one that will be easier to check for divisibility.

10 can be decomposed as:

10 = m - (m-10)

or as

10 = (m+10) - m

such as when we decomposed 10 = 37 - 27 or 10 = 13 - 3

However, as m gets larger, it gets further and further away from 10. (This was the case, for example, when m = 37.) This makes the method less practical as the numbers get larger.

(Note: could rewrite polynomial in terms of 10 as a polynomial in terms of 100...)

Note that it is also possible to divide both sides of the equation N by 10^4,

N / 10^4 = a / 10^4 + b / 10^3 + c / 10^2 + d / 10 + e (mod m)

This works because if N is divisible by m, it is 0 mod m, and so multiplying it by anything (including the inverse of 10^4) will result in it still being 0.

It is necessary to try all of the following:

• Decompose 10 into (m) and (m-10) and see if (m-10) is small (or about 10)
• (Note: if you decompose 10 into (m+10) and m, you're just going to wind up coming full circle with 10 as your coefficient)
• Find inverse of 10 (mod m) and see if it is small (or about 10)

(The question this raises is, do we even need these more complicated divisibility tests, if we can just do a + 10( b + 10( c + 10( d + 10( e) ) ) ) with 10s, straight off, not knowing anything else.)

test for composite numbers

Following the procedure devised for testing divisibility by 8, we can devise divisibility tests for 8 by using the fact that 10 = 2 mod 8, together with the fact that it is sometimes convenient to use 2, and other times convenient to use 10.

Let's examine this in detail.

A three digit number $N=d_{2}d_{1}d_{0}$ can be rewritten:

$N=d_{2}\times 10^{2}+d_{1}\times 10+d_{0}$

or, writing recursively,

$N=((d_{2})\times 10+d_{1})\times 10+d_{0}$

The divisibility test comes down to the question of whether this number is reducible to 0 mod 8:

$N=((d_{2})\times 10+d_{1})\times 10+d_{0}\mod 8$

Now, we can say that 10 = 2 (mod 8), and rewrite the 10s as 2s:

$N=d_{2}\times 2^{2}+d_{1}\times 2+d_{0}$

Okay, let's mix the representations now, and use both 10 and 2:

$N=(d_{2}\times 10+d_{1})\times 2+d_{0}\mod 8$

Now let's write $d_{0}=2\times {\dfrac {d_{0}}{2}}$ and regroup:

$N=(d_{2}\times 10+d_{1}+{\dfrac {d_{0}}{2}})\times 2\mod 8$

Now, because of the constant factor of 2, we can repose this question as follows: does the following quantity reduce to 0 mod 4?

$(d_{2}\times 10+d_{1}+{\dfrac {d_{0}}{2}})\mod 4$

which is equivalent to the rule that says, divide $d_{2}d_{1}d_{0}$ by 10 to yield $d_{2}d_{1}$ and then add the quotient ${\dfrac {d_{0}}{2}}$, and check if it is divisible by 4. If this quantity is divisible by 4, then this quantity times 2 is divisible by 8, and therefore our entire number N is divisible by 8.

Divisibility Test with Multiple Numbers

Divisibility by 3, 7, and 19

The product of the prime numbers 3, 7, and 19 is 399. If a number 100a + b (where b is a two-digit number and a is any positive integer) is divisible by 399 or by any of its divisors, then a + 4b is divisible by this same number.

On your own, can you prove this? (Hint: use 400a + 4b as a link.) Can you formulate and prove its converse?

Devise a simple test of divisibility by 3, 7, and 19.

Divisibility by 7, 11, 13

7, 11, and 13 are 3 consecutive prime numbers. Their product is $7\times 11\times 13=1001$, and when a product is that close to a power of 10, a test of divisibility is not far away.

The test is: separate the number from right to left in groups of 3 digits (the commas conventionally printed in a number do this for you.) Add the groups in even positions and the groups in odd positions. If the difference between the sums is divisible by 7, 11, or 13, the entire number is divisible by 7, 11, or 13, respectively. If the difference is 0, the number is divisible by 7, 11, and 13.

Example: 42,623,295

42,623,295 => ( 623 ) - ( 42 + 295 ) = 286

Now, 286 is divisible by 11 and 13 both, but is not divisible by 7.

Thus, 42,623,295 is divisible by 11 and 13, but not by 7.

Note: 1,000 = 10^3 + 1, and this is a factor of 10^6-1 and 10^9+1. Using these facts, can you demonstrate that the test works on numbers which separate into four groups?

Can you demonstrate the test in general, on your own, two different ways? One can be based on the solution to the problem just shown. The other can be based on the division by 11 trick (mod 11, except use mod 1001 instead of mod 11).