BBC Home

Explore the BBC

Front Page

Life | The Universe | Everything | Advanced Search
 
Front PageReadTalkContributeHelp!FeedbackWho is Online

Click here to complete your registration.

 
3. Everything / Maths, Science & Technology / Mathematics

Divisibility

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 divisible1 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.

A number is
divisible by...
...if...
2it ends with either 0, 2, 4, 6 or 8.
5it ends with either 0 or 5.
10it ends with 0.

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:

A number is
divisible by...
...if...
4its last two digits divide by 4.
8its last three digits divide by 8.
16its last four digits divide by 16.
32its last five digits divide by 32.

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:

A number is
divisible by...
...if...
20the last two digits are 00, 20, 40, 60 or 80.
25the last two digits are 00, 25, 50 or 75.
50the last two digits are 00 or 50.

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.

A number is
divisible by...
...if...
3its digit sum divides by 3.
9its digit sum divides by 9.
11its alternating digit sum divides by 11.

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:

A number is
divisible by...
...if......and...
6it's evenits digit sum divides by 3.
12its last two digits divide by 4its digit sum divides by 3.
15its last digit is 0 or 5its digit sum divides by 3.
18it's evenits digit sum divides by 9.
22it's evenits alternating digit sum divides by 11.
24its last three digits divide by 8its digit sum divides by 3.
27you divide it by 3the digit sum of the result divides by 9.
30it ends in zeroits digit sum divides by 3.
33its digit sum divides by 3its alternating digit sum divides by 11.
36its last two digits divide by 4its digit sum divides by 9.
40it ends in zerothe last two digits before the zero divide by 4.
44its last two digits divide by 4its alternating digit sum divides by 11.
45its last digit is 0 or 5its digit sum divides by 9.
48its last four digits divide by 16its digit sum divides by 3.

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 steps2. 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:

To test for
divisibility by...
...repeatedly......and......then test for
divisibility by...
7Multiply the last digit by 2subtract it from the truncated number7
11Take the last digitsubtract it from the truncated number11
13Multiply the last digit by 4add it to the truncated number13
17Multiply the last digit by 5subtract it from the truncated number17
19Multiply the last digit by 2add it to the truncated number19
23Multiply the last digit by 7add it to the truncated number23
29Multiply the last digit by 3add it to the truncated number29
31Multiply the last digit by 3subtract it from the truncated number31
37Multiply the last digit by 11subtract it from the truncated number37
41Multiply the last digit by 4subtract it from the truncated number41
43Multiply the last digit by 13add it to the truncated number43
47Multiply the last digit by 14subtract it from the truncated number47

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:

A number is
divisible by...
...if......and...
14it divides by 7it's even.
21it divides by 7its digit sum divides by 3.
26it divides by 13it's even.
28it divides by 7its last two digits divide by 4.
34it divides by 17it's even.
35it divides by 7its last digit is 0 or 5.
38it divides by 19it's even.
39it divides by 13its digit sum divides by 3.
42it divides by 7it's even, and its digit sum divides by 3.
46it divides by 23it's even.
49it divides by 7if you divide it by 7, the result also divides by 7.

1 Throughout this entry, we'll use the word 'divisible' to mean 'exactly divisible', ie divisible giving an integer value without remainder.
2 The test also works for divisibility by 11, but it's not as efficient as the test described earlier.

Discuss this Entry  People have been talking about this Guide Entry. Here are the most recent Conversations:

Divide by 2
(Last Posting: Jun 13, 2007)

Divide by
(Last Posting: Jun 12, 2007)

Divison by 4,8,16,32, etc.
(Last Posting: Jun 12, 2007)




Add your Opinion!

There are tens of thousands of h2g2 Guide Entries, written by our Researchers. If you want to be able to add your own opinions to the Guide, simply become a member as an h2g2 Researcher. Tell me More!

 
Entry Data
Entry ID: A23502863 (Edited)

Written and Researched by:
Icy North

Edited by:
Tufty - Squirrel (Un)Extraordinaire


Date: 12   June   2007


Text only
Like this page?
Send it to a friend


Referenced Guide Entries
Numbers
Mathematics
Integers and Natural Numbers
Fractions
Mersenne Numbers
Euclid's Algorithm
42
Zero


Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below.
 


Front PageReadTalkContributeHelp!FeedbackWho is Online

Most of the content on h2g2 is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here. For any other comments, please start a Conversation above.


About the BBC | Help | Terms of Use | Privacy & Cookies Policy