Divisibility Rules Explained

I am no maths genius, and this may be one of the few posts about mathematics on this blog. Here I'll try to explain a bit why divisibility rules work, and maybe try to derive one or two new rules according to that explanation. There are tonnes of articles on internet on this topic, and this is just another one in that crowd.

Basic mathematical concepts used:

1. Every n digit number can be written as sum of n digits multiplied with respective power of 10. These sums can be grouped and compressed suitably.
E.g.
5 = 5*10⁰ = 5*1
13 = 1*10¹ + 3*10⁰ = 1*10 + 3*1 = 13 * 1
467 = 4*10² + 6*10¹ + 7*10⁰ = 4*100 + 6*10 + 7*1 = 46*10 + 7
1234 = 123*10 + 4 = 12*100 + 34 = 1004 + 23*10

2. If X is divisible by Y then for every integer a, a*X is divisible by Y.
E.g. 6 divides 18, hence 6 divides 18 * 5 = 90

3. If Z = X + Y, and X, Y are divisible by T, then Z is divisible by T. This applies even if any of X, Y have negative value.
E.g. 13 divides 65, 91. Hence 13 divides 65 + 91 = 156 and 13 divides -65 + 91 = 26

4. If C =A*B and C divides X then A and B both divide X.
E.g. 6 = 3*2, 6 divides 12 thus 3 and 2 divide 12.

That's all we need. So lets start with simple tests of 2, 4, 8.

Test of 2: The last digit is even (divisible by 2).

Test of 4: The last 2 digits are divisible by 4.

Test of 8: The last 3 digits are divisible by 8.

All three can be explained by same logic.
Consider n digit number A₁A₂A₃..A_n = A₁ * 10ⁿ + .. + A_n = (A₁A₂..A_n-1)*10 + A_n.
Let A = A₁A₂..A_n-1 and B = A_n. So effectively AB is n digit number where A itself is n-1 digit number and B is single digit. Lets call this as length(A) = n-1 and length(B) = 1.

So AB = A*10 + B

Test of 2 says AB divisible by 2 if B divisible by 2.

now 10 is divisible by 2.
=> A*10 divisible by 2 (from Concept 2 above)
so if B divisible by 2 then
A*10 + B divisible by 2 (from concept 3)
=> AB divisible by 2.

Similarly for test of 4,
length(A) = n-2, length(B) = 2
Test of 4 says: B divisible by 4 => AB divisible by 4.

AB = A*100 + B (length(B) = 2)
now 100 divisible by 4
=> A*100 divisible by 4
=> A*100 + B divisible by 4
=> AB divisible by 4

Test of 8:
length(A) = n-3, length(B) = 3
=> AB = A*1000 + B

Test of 8 says, B divisible by 8 => AB divisible by 8.

now 1000 divisible by 8
=> A*1000 divisible by 8
=> A*1000 + B divisible by 8
=> AB divisible by 8

Test of 3: The sum of the digits is divisible by 3

Test of 9: The sum of the digits is divisible by 9

Test of 3 says 4 digit number ABCD = A*1000 + B*100 + C*10 + D is divisible by 3 if A+B+C+D is divisible by 3.

Interesting property about numbers 10, 100, 1000... is that all of them are multiple of 3 + 1. ie 10 = 9 + 1, 100 = 99 + 1. In fact they are multiple of 9 + 1, which is useful in test of 9.

Now let's assume ABCD is divisible by 3.
=> A*1000 + B*100 + C*10 + D is divisible by 3.
=> 999*A + A + 99*B + B + 9*C + C + D is divisible by 3
removing multiples of 3 from above expression
=> A + B + C + D is divisible by 3

This argument is as it is applicable to test of 9, and it can be easily extended to n digit numbers.

Test of 7: If you double the last digit and subtract it from the rest of the number and the answer is divisible by 7.

This is an interesting one. Again lets assume number AB, length(A) = n-1, length(B) = 1 to be divisible by 7.
=> A*10 + B divisible by 7
=> 2*(A*10 + B) divisible by 7
=> A*20 + 2*B divisible by 7
=> 21*A - A + 2*B divisible by 7
=> 2*B - A divisible by 7
=> A - 2*B divisible by 7
which is the test statement.

Test of 11: If you sum every second digit and then subtract all other digits and the answer is divisible by 11.
11 has very interesting property which is all odd powers of 10 i.e. 10^{(2n + 1)} are 1 short of multiple of 11 (e.g. 11, 1001), whereas all even powers of 10 i.e. 10⁽²ⁿ⁾ are 1 excess of multiple of 11 (e.g. 99, 9999).

So let's assume 4 digit number ABCD which is divisible by 11.
=> A*1000 + B*100 + C*10 + D is divisible by 11.
=> A*1001 - A + 99*B + B + 11*C - C + D is divisible by 11.
=> B + D - (A + C) is divisible by 11, which is test statement.

This can be easily extended to n digit numbers.

Test of 5, 10 can be easily proven from test of 2.

So now we have seen logic behind most of the well known tests, let's try to design our own. Let's take 13. I haven't seen any test for 13, so let's see if anything simple enough comes out.

Now 13 does not show any properties like 3, 9, 11 around powers of 10. So that class of tests is not applicable here. Let's try something like test of 7 then.

Let AB be a n digit number with length(A) = n - 1 and length (B) = 1.
Let AB be divisible by 13.
=> A*10 + B is divisible by 13.
Now like test of 7, lets try to make coefficient of A to be 1 and still let it be divisible by 13.
Nearest of 13 multiple for A*10 is 13*A, resulting in -3*A.
=> -3*A + B is divisible by 13.
If we multiply this expression by 4, we get 12*A which is one less than 13's multiple.
=> -12*A  + 4*B divisible by 13.
=> (-13*A + A) + 4*B divisible by 13.
=> A + 4*B is divisible by 13.

Just to remind that this is one of the tests for 13. We can have multiple such by applying different operations to above expression. All of them will be valid as long as operations are applied as per above mentioned rules.

So A + 4*B is a test for 13, which looks good enough to me. Let's try to state it in words:
A_ny number is divisible by 13 if you multiply the last digit by 4 and add it to the rest of the number and the answer should be divisible by 13. This can be recursively applied.

Let's verify if this is correct:
26459 is not divisible by 13. Lets test it on our expression:
=>2645 + 9*4 = 2681
=>268+4=272
=>27+8=35 => Not divisible by 13.

4632199 is divisible by 13. Lets see if our test shows it:
=>4632199
=>463219 + 36 = 463255
=>46325 + 20 = 46345
=>4634 + 20 = 4654
=>465 + 16 = 481
=>48 + 4 = 52
which is divisible by 13

We can apply similar methodology to derive test for other numbers.
Test of 17:
10x+y => -7x + y => -35x + 5y
=> x - 5y

Test of 19:
10x + y => 20x + 2y 
=> x + 2y

So that's it for this post. If you have any interesting fact about any divisibility test mentioned/ not mentioned here, please comment.

                                                                                                                              ASD