One of the oldest mathematical problems known to man is divisibility. If you divide a number of items equally among a number of people, will there be any items left over at the end? If you cut a length of wood into four-feet-long planks, will any of it be wasted? The problem crops up time and time again in different situations.

Factorisation Problems

Another common divisibility problem occurs when we have large fractions - like 8,778 / 2,772, say, which we want to simplify and write in their lowest terms. It's handy to be able to factorise the numbers, ie, determine which numbers would multiply together to make them. Where the top and bottom of the fraction share a common factor, then we know we can divide each by this to get the same fraction expressed in a simpler way.

So, what are the common factors of 8,778 and 2,772? In the 3rd Century BC, the Greek mathematician Euclid came up with his famous common divisor algorithm, which identifies the largest common factor between two numbers. This is a very efficient way to express a fraction in its lowest terms, but if we wanted to check for a specific factor, or list all the factors, then specific divisibility tests can be very useful too.

Going back to our example, 8,778 / 2,772, we can identify some small factors easily. The top and bottom numbers are both even, and so they divide by 2, reducing our fraction to 4,389 / 1,386. Now, the top number is no longer even, so we can't repeat this and divide by 2 again.

You may know another trick, involving divisibility by 3. If you add together all the digits of a number, and the sum divides by 3, then the number itself divides by 3. As our top number's digits added together make 24, and our bottom number's digits added together make 18 - both divisible by 3 - then we can indeed divide them both by 3, giving the fraction 1,463 / 462. We could repeat this test, but it would not be successful in this case: the top number, 1,463, is no longer divisible¹ by 3.

That's where most of us would come unstuck, but in fact both numbers divide by 7 and 11, too. Divide top and bottom by these, and our fraction in its simplest form turns out to be 19/6, something which is far easier to work with than 8,778 / 2,772.

So, we can see that those tricks involving divisibility by 2 and 3 are pretty useful, and it would be good if we could extend these to include numbers like 7 and 11, too. In fact, divisibility tests exist for most numbers, and that is the subject of this entry. We'll cover techniques for each of the numbers between 2 and 50.

Divisibility by 2, 5 and 10

We'll start with the trivial ones. These particular tests are dead simple because we work in a base 10 (decimal) number system. As 2, 5 and 10 are factors of 10, we only need to inspect the last digit of a number to decide whether it is divisible by each of these.

Divisibility by 4, 8, 16 and 32

Now, if we can divide a number by 2 and the result is still even, then we can divide it by 2 again: the original number divides by 4. OK, it's a divisibility test and it works, but what about large numbers, like 98,284,828,482? Maybe it's too long to type into your pocket calculator. We would have to go through the division manually, which takes time.

You'll be pleased to know that there is a quicker way. If you consider the number as 98,284,828,400 + 82, then you can see that the first part divides by 100, and therefore it divides by 4. We need to consider only the last two digits. If they divide by 4, then so does the larger number.

In fact, 82 doesn't divide by 4, it comes to 20.5, and so 98,284,828,482 isn't divisible by 4 either. You may not even need to do the division on the final two digits - two-digit numbers divisible by 4 are often recognisable as leap years or summer Olympic years.

Similarly, 1,000 divides by 8, so any number whose last three digits divide by 8 is itself divisible by 8. In this case, you'll probably need to do the division - the quickest way could be to divide the last three digits by 2 and see if the last two digits of your result are divisible by 4 (see above).

This method extends to higher powers of 2, so to summarise, we have:

Divisibility by 20, 25 and 50

In a similar way, 100 divides by 20, 25 and 50, so we need to consider only the last two digits of a number to tell if it is divisible by these:

Divisibility by 3, 9 and 11

We mentioned earlier that if you add up all the digits of a number and the sum is divisible by 3, then the number itself is also divisible by 3. It's interesting to consider why. It's actually a consequence of working in base 10. Every power of 10 has the remainder 1 when you divide it by 3. Now, let's take a number like 854, say. You can write this as 800 + 50 + 4. The 800 part has the remainder 2 when you divide it by 3. This is because 8 has remainder 2 and 100 has remainder 1, so 800 (8 x 100) has the remainder 2 (2 x 1). So 800's remainder is the same as 8's remainder. Similarly, 50's remainder is the same as 5's, and the same goes for all the other digits of a number. It follows that you only need to add the digits of a number to get a smaller number which generates the same remainder.

Powers of 10 also have the remainder 1 when you divide them by 9, so exactly the same test can be used to check divisibility by 9.

There is also a similar test for divisibility by 11. You need to alternately add and subtract consecutive digits of the number, and if the result is divisible by 11, then so is the larger number. Using our big number, 98,284,828,482, as an example, we get +9-8+2-8+4-8+2-8+4-8+2, the result of which is -17. We call this the 'alternating digit sum' of the number. In fact, 17 isn't divisible by 11, so neither is 98,284,828,482.

This test works because the remainder when you divide 1, 100, 10,000 etc by 11 is 1 and the remainder when you divide 10, 1,000, 100,000 by 11 is 10, or alternatively minus 1. It follows that the alternating digit sum of a number will give the same remainder as the number itself.

Divisibility by Simple Multiples

Before we get on to some of the more difficult tests, it's worth mentioning that you can combine the above tests to confirm divisibility for numbers which are multiples of them. For example, 12 divides any number which is divisible by both 3 and 4. If a number's digit sum is divisible by 3, and its last two digits are divisible by 4, then it divides by 12, and so on:

Divisibility by 7 and 13

From this point, divisibility tests get a little more time-consuming, but with practice, they should still be a little quicker than performing the division outright.

For divisibility by 7 or 13, you need to follow these steps². We'll use as an example our big number, 98,284,828,482, which we'll test for divisibility by 7:

1. Split the number into groups of three digits, starting from the unit (smallest value) digit. (We get 98 284 828 482)

2. Divide each group of digits by 7, and remember the remainder. (We get 98/7 = zero, 284/7 = 4, 828/7 = 2, 482/7 = 6)

3. Alternately add and subtract these remainders. (We get 0-4+2-6 = -8)

4. If the result divides exactly by 7, then the number itself divides by 7. (8 is not divisible by 7, so neither is 98,284,828,482)

To test for divisibility by 13, follow the same steps, but replace 7 with 13 throughout. You may find your 13-times table handy!

To explain how this technique works would be a little beyond the scope of this entry, but if you want to investigate it for yourself, it's a consequence of 7 and 13 both being factors of the number 1,001.

Tests for Larger Prime Numbers

To test divisibility by the remaining prime numbers, there exists a very clever technique for simplifying the number. It also works for 7, 11 and 13, so you may find it a useful alternative to the tests described previously for those numbers.

We'll start with an example; we'll test 8,778 for divisibility by 7. You need to follow these steps:

1. Separate the last digit from the number.
   (We get 877 and 8)

2. Double the last digit and then subtract it from the rest of the number.
   (8 x 2 = 16, 877 - 16 = 861)

3. Repeat the first two steps until you have a number which you can easily test for divisibility by 7.
   (We repeat the test: 861 separates to 86 and 1, 1 x 2 = 2, 86 - 2 = 84. We could repeat the test again, but 84 is recognisable as being divisible by 7 - it's 7 x 12. It follows that 8,778 is also divisible by 7.)

Now, this test is slightly different depending on which number you are testing for. For divisibility by 13, you would multiply the separated digit by 4, and add it to the truncated number. The following table shows the tests for all the prime numbers between 7 and 47:

Note that some of these tests require a bit of mental arithmetic. You may need to know your 13- or 14-times table, so it may be helpful to write these down before you start.

The test works for prime numbers only. To explain how it works would again be a little beyond the scope of this entry, but we choose the multiplier for each test number as described below. This will help you remember the particular values for each test:

• We need to find the smallest multiple of our prime number which ends in either a 1 or a 9.

• The digits before the 1 or 9 become our last-digit multiplier in the test, but if it's a 9, we add 1 to this multipler.

• If the multiplied prime number ends in a 1, then our test will subtract the multiple of the last digit from the truncated number.

• Alternatively, if the multiplied prime number ends in a 9, then our test will add the multiple of the last digit to the truncated number.

So, in the case of our test for 7, the smallest multiple of 7 which ends in 1 or 9 is 21. The digit before 1 is 2. So we will repeatedly subtract twice the last digit from the truncated number.

Divisibility by the Remaining Multiples

We'll finish by listing the tests for the remaining non-prime numbers - those which have more difficult prime factors: