original Indian

Divisibility Tests to 50 and Beyond

We know that to test for divisibility by (say) 15, we need only test for divisibility by 3 and 5. It follows that only the prime divisibility tests are required.
All the methods here work in the same recursive way. The number N1 is a multiple of prime P if (and only if) the smaller number N2 is also a multiple of P. These algorithms provide a way of reducing N1 to N2 (and N3, N4 etc.) until a multiple of P is recognised.
Some examples
We wish to test the number 742 (N1) for divisibility by 7. We get to the smaller number (N2) by chopping off the units digit, multiplying it by 5 and adding it to the number of tens in the orginal number (N1):
742 -> 74 + (2 x 5) = 84, which is clearly a multiple of 7
Therefore 742 is also a multiple of 7.
Another example. Is 3647 divisible by 7?
3647 -> 364 + (7 x 5) = 399
399 -> 39 + (9 x 5) = 84, which is a multiple of 7.
Therefore 3647 is also a multiple of 7 (and incidentally, so is 399).
I shall call this algorithm "Multiply by 5 and add".
The algorithm "Multiply by 2 and subtract" also works as a test for divisibility by 7:
3647 -> 364 - (7 x 2) = 350
350 -> 35 - (0 x 2) = 35, which is a multiple of 7
Therefore 3647 is also a multiple of 7 (and incidentally, so is 350).
These two algorithms form a "conjugate pair", one being "add" and the other being "subtract", as well as one being "multiply by m" and the other being "multiply by (p-m)", where p in this case is 7.
All this is leading up to the remaining divisibility tests. Each one uses the basic procedure of chopping off the units digit, multiplying it by m [or (p-m)] and then either adding to or subtracting from the truncated number.
Why These Methods Work
The simplest explanation, which is usually good enough for children, is that the procedure is just a fancy way of doing division by "chunking" - i.e., removing known multiples and just testing the remainder.
The Real Reason
The algorithm creates a smaller number that is a multiple of the prime being tested if and only if the original number was also a multiple. The explanation for the 7 test:
The original number (N1) can be written in the form 10a + b. For example, if N1 is 742 then a = 74 and b = 2.
Let's assume that 10a + b is a multiple of 7. Then 10a + b = 7k for some integer value of k.
Then b = 7k - 10a.
And a + 5b = a + 35k - 50a = 35k - 49a = 7 (5k - 7a)
So this is clearly a multiple of 7 as well.
The General Procedure
The trick is simply to find the multiplying factor (m) for each number (p) to be tested. Playing with the algebra reveals that m is simply the first integer for which 10m-1 is divisible by p. The conjugate factor (p-m) is similarly the first integer for which 10(p-m)+1 is divisible by p. This gives the following table:
Divisibility Test (p)
Factor (m)
Conjugate Factor (p-m)
Best Algorithm
7
5
2
x5 and add
11
10
1
x10 and add
13
4
9
x4 and add
17
12
5
x5 and subtract
19
2
17
x2 and add
23
7
16
x7 and add
29
3
26
x3 and add
31
28
3
x3 and subtract
37
26
11
x11 and subtract
41
37
4
x4 and subtract
43
13
30
(either)
47
33
14
(either)
53
16
37
(either)
Let’s use the table to test whether 3534 is divisible by 31. The algorithm is "Multiply by 3 and subtract":
3534 -> 353 - (4 x 3) = 341
341 -> 34 - (1 x 3) = 31 which is a multiple of 31
Therefore 3534 is divisible by 31.
Dividing by 3
Add up the digits: if the sum is divisible by three, then the number is as well. Examples:
111111: the digits add to 6 so the whole number is divisible by three.
87687687. The digits add up to 57, and 5 plus seven is 12, so the original number is divisible by three.
Why does the 'divisibility by 3' rule work?
Divisibility of a number by 3

The only way that I can think of to explain this would be as follows: Look at a 2 digit number: 10a+b=9a+(a+b). We know that 9a is divisible by 3, so 10a+b will be divisible by 3 if and only if a+b is. Similarly, 100a+10b+c=99a+9b+(a+b+c), and 99a+9b is divisible by 3, so the total will be iff a+b+c is.
This explanation also works to prove the divisibility by 9 test. It clearly originates from modular arithmetic ideas, and I'm not sure if it's simple enough, but it's the only explanation I can think of.

Dividing by 4
Look at the last two digits. If the number formed by its last two digits is divisible by 4, the original number is as well. Examples:
100 is divisible by 4.
1732782989264864826421834612 is divisible by four also, because 12 is divisible by four.
Dividing by 5
If the last digit is a five or a zero, then the number is divisible by 5.
Dividing by 6
Check 3 and 2. If the number is divisible by both 3 and 2, it is divisible by 6 as well.
Robert Rusher writes in: Another easy way to tell if a [multi-digit] number is divisible by six . . .is to look at its [ones digit]: if it is even, and the sum of the [digits] isa multiple of 3, then the number is divisible by 6.

Dividing by 7
To find out if a number is divisible by seven, take the last digit, double it, and subtract it from the rest of the number. Example: If you had 203, you would double the last digit to get six, and subtract that from 20 to get 14. If you get an answer divisible by 7 (including zero), then the original number is divisible by seven. If you don't know the new number's divisibility, you can apply the rule again.

Matthew Correnti describes this method: If you do not know if a two-digit number, call it ab, is divisible by 7, calculate 2a + 3b. This will yield a smaller number, and if you do the process enough times you will eventually -- if the number ab is divisible by 7 -- end up with 7. You can use a similar method if you have a three-digit number abc: take the digit a and multiply it by 2, then add it to the number bc, giving you 2a + bc; repeat and reduce until you recognize the result's divisibility by seven. With a four-digit number abcd, take the digit a and multiply by 6, then add 6a to bcd giving. This usually gives you a three-digit number; call it xyz. Take that x and, as described previously, multiply x by two and add to yz (i.e., 2x + yz). Again, repeat and reduce until you recognize the result's divisibility by seven.
Ahmed Al Harthy writes in: To know if a number is a multiple of seven or not, we can use also 3 coefficients (1 , 2 , 3). We multiply the first number starting from the ones place by 1, then the second from the right by 3, the third by 2, the fourth by -1, the fifth by -3, the sixth by -2, and the seventh by 1, and so forth. Example: 348967129356876. 6 + 21 + 16 - 6 - 15 - 6 + 9 + 6 + 2 - 7 - 18 - 18 + 8 + 12 + 6 = 16 means the number is not multiple of seven. If the number was 348967129356874, then the number is a multiple of seven because instead of 16, we would find 14 as a result, which is a multiple of 7. So the pattern is as follows: for a number onmlkjihgfedcba, calculate a + 3b + 2c - d - 3e - 2f + g + 3h + 2i - j - 3k - 2l + m + 3n + 2o. Example: 348967129356874. Below each digit let me write its respective figure. 3 4 8 9 6 7 1 2 9 3 5 6 8 7 6 2 3 1 -2 -3 -1 2 3 1 -2 -3 -1 2 3 1 (3×2) + (4×3) + (8×1) + (9×-2) + (6×-3) + (7×-1) + (1×2) + (2×3) + (9×1) + (3×-2) + (5×-3) + (6×-1) + (8×2) + (7×3) + (6×1) = 16 -- not a multiple of seven.
Another visitor observes: Here is one formula for seven... 3X + L L = last digitX = everything in front of last digit. All numbers that are divisible by seven have this in common. There are no exceptions. For example, 42: 3(4) + 2 = 14.Seven divides into 14, so it divides into 42. Next example, 105: 3(10) + 5 = 35.Seven divides into 35, so it divides into 105. Here is another formula for seven: 4X - L When using this formula, if you get zero, seven or a multiple of seven, the number will be divisible by seven. For example, 56: 4(5) - 6 = 14.Seven divides into 14, so it divides into 56. Next example, 168: 16(4) - 8 = 56.Seven divides into 56, so it divides into 168. Similarly: The formula for 2 is 2X + LThe formula for 3 is 4X + LThe formula for 4 is 6X + LThe formula for 5 is 5X + LThe formula for 6 is 2X + L and 4X + L -- in other words, the formulas for 2 and 3 must work before the number is divisible by 6.The formula for 9 is X + LThe formula for 11 is X - LThe formula for 12 is 2X - LThe formula for 13 is 3X - LThe formula for 14 is 4X - L and 2X + L -- in other words, the formulas for 7 and 2 must work before the number is divisible by 14.The formula for 17 is 7X - LThe formula for 21 is X - 2LThe formula for 23 is 3X - 2LThe formula for 31 is X - 3L
Sara Heikali explains this way to test a number with three or more digits for divisibility by seven: 1. Write down just the digits in the tens and ones places.2. Take the other numbers to the left of those last two digits, and multiply them by two.3. Add the answer from step two to the number from step one.4. If the sum from step three is divisible by seven, then the original number is divisible by seven, as well. If the sum is not divisible by seven, then the original number is not divisible by seven. For example, if the number we are testing is 112, then1. Write down just the digits in the tens and ones places: 12.2. Take the other numbers to the left of those last two digits, and multiply them by two: 1 × 2 = 2.3. Add the answer from step two to the number from step one: 12 + 2 = 14.4. Fourteen is divisible be seven. Therefore, our original number, one hundred twelve, is also divisible by seven.

Dividing by 8
Check the last three digits. Since 1000 is divisible by 8, if the last three digits of a number are divisible by 8, then so is the whole number.Example: 33333888 is divisible by 8; 33333886 isn't.
How can you tell whether the last three digits are divisible by 8? Phillip McReynolds answers:
If the first digit is even, the number is divisible by 8 if the last two digits are. If the first digit is odd, subtract 4 from the last two digits; the number will be divisible by 8 if the resulting last two digits are. So, to continue the last example, 33333888 is divisible by 8 because the digit in the hundreds place is an even number, and the last two digits are 88, which is divisible by 8. 33333886 is not divisible by 8 because the digit in the hundreds place is an even number, but the last two digits are 86, which is not divisible by 8.
Sara Heikali explains this test of divisibility by eight for numbers with three or more digits: 1. Write down the units digit of the original number.2. Take the other numbers to the left of the last digit,and multiply them by two.3. Add the answer from step two to the number from step one.4. If the sum from step three is divisible by eight, then the original number is divisible by eight, as well. If the sum is not divisible by eight, then the original number is not divisible by eight. For example, if the number we are testing is 104, then1. Write down just the digits in ones place: 4.2. Take the other numbers to the left of that last digit,and multiply them by two: 10 × 2 = 20.3. Add the answer from step two to the number from step one:4 + 20 = 24.4. Twenty-four is divisible be eight. Therefore, our originalnumber, one hundred and four, is also divisible by eight.
Dividing by 9
Add the digits. If that sum is divisible by nine, then the original number is as well.
Dividing by 10
If the number ends in 0, it is divisible by 10.
Dividing by 11
Let's look at 352, which is divisible by 11; the answer is 32. 3+2 is 5; another way to say this is that 35 -2 is 33.
Now look at 3531, which is also divisible by 11. It is not a coincidence that 353-1 is 352 and 11 × 321 is 3531.
Here is a generalization of this system. Let's look at the number 94186565.
First we want to find whether it is divisible by 11, but on the way we are going to save the numbers that we use: in every step we will subtract the last digit from the other digits, then save the subtracted amount in order. Start with 9418656 - 5 = 9418651 SAVE 5 Then 941865 - 1 = 941864 SAVE 1 Then 94186 - 4 = 94182 SAVE 4 Then 9418 - 2 = 9416 SAVE 2 Then 941 - 6 = 935 SAVE 6 Then 93 - 5 = 88 SAVE 5 Then 8 - 8 = 0 SAVE 8
Now write the numbers we saved in reverse order, and we have 8562415, which multiplied by 11 is 94186565.
Here's an even easier method, contributed by Chis Foren:
Take any number, such as 365167484.
Add the first, third, fifth, seventh,.., digits.....3 + 5 + 6 + 4 + 4 = 22
Add the second, fourth, sixth, eighth,.., digits.....6 + 1 + 7 + 8 = 22
If the difference, including 0, is divisible by 11, then so is the number.
22 - 22 = 0 so 365167484 is evenly divisible by 11.

Dividing by 12
Check for divisibility by 3 and 4.

Dividing by 13
Here's a straightforward method supplied by Scott Fellows:
Delete the last digit from the given number. Then subtract nine times the deleted digit from the remaining number. If what is left is divisible by 13, then so is the original number.
Rafael Ando contributes:
Instead of deleting the last digit and subtracting it ninefold from the remaining number (which works), you could also add the deleted digit fourfold. Both methods work because 91 and 39 are each multiples of 13.
For any prime p (except 2 and 5), a rule of divisibility could be "created" using this method:
2. Find m, such that m is the (preferably) smallest multiple of p that ends in either 1 or 9.
3. Delete the last digit and add (if multiple ends in 9) or subtract (if it ends in 1) the deleted digit times the integer nearest to m/10. For example, if m = 91, the integer closest to 91/10 = 9.1 is 9; and for 3.9, it's 4.
4. Verify if the result is a multiple of p. Use this process until it's obvious.
Example 1: Let's see if 14281581 is a multiple of 17. In this case, m = 51 (which is 17×3), so we'll be deleting the last number and subtracting it fivefold.
1428158 - 5×1 = 1428153 142815 - 5×3 = 142800 14280 - 5×0 = 14280 1428 - 5×0 = 1428 142 - 5×8 = 102 10 - 5×2 = 0, which is a multiple of 17, so 14281581 is multiple of 17.
Example 2: Let's see if 7183186 is a multiple of 46. First, note that 46 is not a prime number, and its factorization is 2×23. So, 7183186 needs to be divisible by both 2 and 23. Since it's an even number, it's obviously divisible by 2. So let's verify that it is a multiple of 23:
m = 3×23 = 69, which means we'll be adding the deleted digit sevenfold. 718318 + 7×6 = 718360 71836 + 7×0 = 71836 7183 + 7×6 = 7225 722 + 7×5 = 757 75 + 7×7 = 124 12 + 7×4 = 40 4 + 7×0 = 4 (not divisible by 23), so 7183186 is not divisible by 46.
Note that you could've stopped calculating whenever you find the result to be obvious (i.e., you don't need to do it until the end). For example, in example 1 if you recognize 102 as divisible by 17, you don't need to continue (likewise, if you recognized 40 as not divisible by 23). The idea behind this method it that you're either subtracting m×(last digit) and then dividing by 10, or adding m×(last digit) and then dividing by 10.
Jeremy Lane adds:
It may be noted that while applying these rules, it is possible to loop among numbers as results.
Example: Is 1313 divisible by 13? Using the procedure given we take 13×3 and obtain 39. This multiple ends in 9 so we add four-fold the last digit.
131 + 4×3 = 143 14 + 4×3 = 26 2 + 4×6 = 26 ...
Example: Is 1326 divisible by 13? Using the procedure given we take 13×7 = 91. This is not the smallest multiple, but it does show looping. The smaller multiple does loop at 39 as well. There are some examples where we would still need to recognize certain multiples. So we subtract nine-fold the last digit.
132 - 9×6 = 78 7 - 9×8 = -65 (factor out -1) 6 - 9×5 = -39 (again factor out -1) 3 - 9×9 = -78 (factor out -1)
This only occurs though if the number does happen to be divisible by the prime divisor. Otherwise, eventually you will have a number that is less than the prime divisor.
And here's a more complex method that can be extended to other formulas: 1 = 1 (mod 13)10 = -3 (mod 13) (i.e., 10 - -3 is divisible by 13)100 = -4 (mod 13) (i.e., 100 - -4 is divisible by 13)1000 = -1 (mod 13) (i.e., 1000 - -1 is divisible by 13)10000 = 3 (mod 13)100000 = 4 (mod 13)1000000 = 1 (mod 13)
Call the ones digit a, the tens digit b, the hundreds digit c, ..... and you get:
a - 3×b - 4×c - d + 3×e + 4×f + g - .....
If this number is divisible by 13, then so is the original number.
You can keep using this technique to get other formulas for divisibility for prime numbers. For composite numbers just check for divisibility by divisors.
Dividing by 14
Sara Heikali builds on her divisibility test for seven: How can you know if a number with three or more digits is divisible by the number fourteen? Check if the last digit of the original number is odd or even. If the number is odd, then the number is not divisible by fourteen. If the number is even, then apply the divisibility rule for seven. (Keep in mind, the odd and even test is to see if the number is divisible by two.) If the original even number is divisible by seven, then it is also divisible by fourteen. If the original even number is not divisible by seven, it is not divisible by fourteen.
Divisibility by:
2
If the last digit is even, the number is divisible by 2.
3
If the sum of the digits is divisible by 3, the number is also.
4
If the last two digits form a number divisible by 4, the number is also.
5
If the last digit is a 5 or a 0, the number is divisible by 5.
6
If the number is divisible by both 3 and 2, it is also divisible by 6.
7
Take the last digit, double it, and subtract it from the rest of the number; if the answer is divisible by 7 (including 0), then the number is also.
8
If the last three digits form a number divisible by 8, then so is the whole number.
9
If the sum of the digits is divisible by 9, the number is also.
10
If the number ends in 0, it is divisible by 10.
11
Alternately add and subtract the digits from left to right. (You can think of the first digit as being 'added' to zero.)If the result (including 0) is divisible by 11, the number is also.Example: to see whether 365167484 is divisible by 11, start by subtracting: [0+]3-6+5-1+6-7+4-8+4 = 0; therefore 365167484 is divisible by 11.
12
If the number is divisible by both 3 and 4, it is also divisible by 12.
13
Delete the last digit from the number, then subtract 9 times the deleted digit from the remaining number. If what is left is divisible by 13, then so is the original number.