divisibility tests

Divisibility tests allow us to calculate whether a number can be divided by another number.  For example, can 354 be divided by 3?  Can 247,742 be divided by 11?  So what are the rules behind divisibility tests, and more interestingly, how can we prove them?

Divisibility rule for 3

The most well known divisibility rule is that for dividing by 3.  All you need to do is add the digits of the number and if you get a number that is itself a multiple of 3, then the original number is divisible by 3.  For example, 354 is divisible by 3 because 3+5+4 = 12 and 12 can be divided by 3.

We can prove this using the modulo function.  This allows us to calculate the remainder when any number is divided by another.  For example, 21 ≡ 3 (mod 6).  This means that the remainder when 21 is divided by 6 is 3.

So we first start with our number that we want to divide by 3:

n = a + 10b + 100c + 1000d + …….

Now, dividing by 3 is the same as working in mod 3, so we can rewrite this n in terms of mod 3:

n = a + 1b + 1c + 1d + ……. (mod 3)

(this is because 10 ≡ 1 mod 3, 100 ≡ 1 mod 3, 1000 ≡ 1 mod 3 etc)

Now, for  a number to be divisible by 3 this sum needs to add to a multiple of 3.  Therefore if a + b + c + d + …. ≡ 0 (mod 3) then the original number is also divisible by 3.

Divisibility rule for 11

This rule is much less well known, but it’s quite a nice one.  Basically you take the digits of any number and alternately subtract and add them.  If the answer is a multiple of 11 (or 0) then the original number is divisible by 11.  For example, 121 is a multiple of 11 because 1-2+1 = 0.  247,742 is because 2-4+7-7+4-2 = 0.

Once again we can prove this using the modulo operator.

n = a + 10b +100c + 1000d + …..

and this time work in mod 11:

n = a + -1b +1c + -1d + ….. (mod 11)

this is because for ease of calculation we can write 10 ≡ -1 (mod 11).  This is because -1 ≡ 10 ≡ 21 ≡ 32 ≡ 43 (mod 11).  All numbers 11 apart are the same in mod 11.  Meanwhile 100 ≡ 1 (mod 11).  This alternating pattern will continue.

Therefore if we alternately subtract and add digits, then if the answer is divisible by 11, then the original number will be as well.

Palindromic Numbers

Palindromic numbers are numbers which can be read the same forwards as backwards.  For example, 247,742 is a palindromic number, as is 123,321.  Any palindromic number which is an even number of digits is also divisible by 11.  We can see this by considering (for example) the number:

n = a + 10b + 100c + 1000c + 10,000b + 100,000a

Working in mod 11 we will then get the same pattern as previously:

n = a – b +c – c +b – a (mod 11)

so n = 0 (mod 11).  Therefore n is divisible by 11.  This only works for even palindromic numbers as when the numbers are symmetric they cancel out.