Weirdly: adv. In a strikingly odd or unusual manner
< Older Blog - The Latest - Pick One - Show All - Newer Blog >

14-11-2009 Tricks for Testing Divisibility

There are several useful tricks that are often taught in grade school for checking the divisibility of numbers. These vary in complexity, the reason for their working ranging from the very obvious to the very obscure.

Basically...

The base in which we express numbers is a key part of the work explored here. It is important then to understand what we mean by a numeric base. This is quite often and quite incorrectly thought of by people as weird, complicated stuff; I have heard countless comments of not "getting" it. It is in fact fairly elementary math that almost everyone already understands the background of. In fact, there are no new tricks or concepts to learn. The only mathematical ideas that are needed are among those taught to us in grade school: additon, multiplication, and exponents.

Consider the way we express a number. Let's take my birth year, nineteen-seventy-six. we normally express that as:

1976

Now consider the individual digits in that number, 1, 9, 7 and 6. As we're all taught in our earliest years, those digits each fall into a column, often referred to as "ones", "tens", "hundreds", etc. We call them that because the digit in that column does not actually represent its own value, but a multiple of its own value. When we look at this number, we don't think of it as being simply "1 + 9 + 7 + 6". Instead, we see that it means "1000 + 900 + 70 + 6". That can also be expresed as:

1×1000 + 9×100 + 7×10 + 6×1

or:

1×103 + 9×102 + 7×101 + 6×100

In other words, each column represents a power of ten that is multiplied by the number in that column. Those powers increment with each column from right to left.

Other numeric bases work exactly the same way. The only difference between them is the base, ie. the number that those exponents are applied to. Normally that base is ten because we have ten unique symbols that represent the first ten values, 0 through 9. There is nothing preventing us from using other numbers though. For example, computers use binary, or "base two" numbers. These work exactly the same way as decimal, but instead of having ten unique symbols, it only has two, "0" and "1". As a result, the columns used in expressing the numbers are not powers of ten, but powers of two. Instead of ones, tens, hundreds, etc. the columns in a binary number are ones, twos, fours, eights and so on. So the same number we used above, rather than being expressed as "1976", would instead be:

11110111000

If you break it down and convert it back to decimal, it comes out like this:

1×210 + 1×29 + 1×28 + 1×27 + 0×26 + 1×25 + 1×24 + 1×23 + 0×22 + 0×21 + 0×20

or:

1024 + 512 + 256 + 128 + 0 + 32 + 16 + 8 + 0 + 0 + 0
= 1976

This same technique of expressing numbers works in any numeric base. For example, in "hexadecimal", or base 16, we would use 16 unique symbols, rather than 10. The standard there is to use letters as additional symbols, so the digits in use would be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. That same number would then be expressed as "7B8", or:

7×102 + B×101 + 8×100

which, if we convert back to decimal, would be:

7×162 + 11×161 + 8×160
= 7 × 256 + 11 × 16 + 8 × 1
= 1792 + 176 + 8
= 1976

Some time ago, a friend and I were discussing the reason behind a method for testing whether or not a number is divisibile by three. In figuring out the logic of it, I developed a bit of a curiosity for these techniques, and the application of them in other numeric bases. The purpose of this writing is to explore some of the commonly known ones, and rewrite them in a way that can be applied in any base (see sidenote).

To start out, let's take a look at some of the most common tricks for checking the divisibility of a number. A number is divisible by:

Many of these methods can be grouped together in more generic terms, because they follow similar rules. For example, 2 and 5 work in the same way, as do 3 and 9. It is a generic version of each of these rules that we will explore here.

Numbers ending with 0's

Starting with the simplest one then. If the last digit of a number is a 0, then that number is divisible by ten. This is because of the way our notation works. For each ten numbers we count, we reset the first column to 0, and increment the next column by one. This applies to any numeric base, and always for the number represented by the symbols "10". In binary then, the last digit being a 0 means the number is divisible by two. In hexidecimal, that closing zero means it's divisible by 16. More exactly then, a number is divisible by the base in which it's expressed if the last digit of the number is a 0.

That can of course be expanded upon to include divisibility by 100, 1000 and so on. One might say that an integer can always be divided by the base in which it's written, raised to the power of as many 0's as there are on the right end of that integer. This statement holds true even if there are no zeros at the end of the number. In that case, we're saying that the number is divisible by 100, which equals one.

Factors of the base we're working in

The next simplest trick is the one we apply to both division by 2 and division by 5. At first glance, those two may seem to work differently, but they are in fact identical. Each of those tricks works because the number we're dividing by is a factor of the base we're working in. This is why it only applies to 2 and 5 when we're working in regular decimal arithmetic; those are the only two factors of ten.

Because they're factors of ten, when we count multiples of these numbers, the "ones" column in our number will always be a multiple of these numbers. Consider keeping a tally, starting at 0 and incrementing it by 5. You would get the values 5, 10, 15, 20, 25, and so on. You can see that the rightmost digit gets reset to zero each time our tally hits a multiple of ten. Because 5 is a factor of 10, our tally will hit every multiple of ten. As a result of that, the rightmost column will always be a value that is a multiple of this number which is less than 10. That applies equally to multiples of 2, only we're dealing with a larger set of multiples. Instead of 0 and 5, we have 0, 2, 4, 6 and 8.

This same rule can be applied in any other base as long as the base is not a prime number. A good example of this would be base 12 notation. Because 12 has more factors than 10, we can apply it more broadly. In base 12:

We can say then that if X is a factor of the base we're working in, then a number is divisible by X if its last digit is a multiple of X.

Divisibility of a limited set of digits

This is a trick that is commonly applied to check for multiples of 4 and 8. If the rightmost two digits form a number that is divisible by 4, then the number itself is as well. Similarly, if the last three digits are divisible by 8, then the entire number is. This is in fact a slightly more complicated version of the same method we use to check for divisibility by 5 and 2.

It works with the number 4 because in decimal, the number that we express as "100" is divisible by 4. This means that the last two digits will go through a limited set of combinations (25 specifically), before they get reset to 00. The other effect of this is that the same last pair of digits will be used no matter what combination of remaining digits is in place. As a result of this, we can see if 4 is a factor of a number simply by seeing if 4 is a factor of its last two digits.

The same technique works with the number 8. The only difference here being that 8 is not a factor of 100 (ie. 102), but of 1000 (103). Because of this, we have to check the last three digits instead of the last two.

This can of course be applied in other numeric bases as well. One such example would be in base 12 notation when checking multiples of 8 or 9. This works because 8 and 9 are both factors of 122, but not of 12 itself.

To formally state this trick then, we can say that where B is the base in which a number is expressed, if BP is divisible by X, then X will be a factor of any number whose last P digits are divisible by X.

Counting the sum of the digits

This is a technique that we use for multiples of 9 and 3. To check (in regular decimal notation) whether a number is divisible by three, simply add its digits together. If the sum of those digits is divisible by three, then the number itself is. This is applied to multiples of 9 in the same way. If the sum of the digits is divisible by 9, then the number itself is too.

One neat aspect of this is that you can apply it recursively. For example, to see if 4897284 is divisible by three, just add its digits: 4 + 8 + 9 + 7 + 2 + 8 + 4 = 42. Still not sure? then simply add those digits: 4 + 2 = 6. Six is divisible by 3, so you know that 42 is as well, and therefore 4897284 is also.

The reason this works is rather interesting, and I have actually explained it in depth in an earlier blog. Here though is a short answer:

This happens because the number we're testing for has a multiple that is exactly 1 less than the base we're working in. This is easiest to see when working with multiples of 9. Looking at those, you get 9, 18, 27, 36, 45, 54, 63, 72, and so on. It is important to note that each time the "tens" column is increased by 1, the "ones" column is decreased by 1. This means that the two columns will always balance each other out. It is the fact that 9 is one less than the base we're using that allows this to happen.

This also applies to other bases as well. For example, in hexadecimal (base 16), this would apply to the numbers 3, 5, and E. Take the multiples of 5 for example: 5, A, E 14, 19, 1D, 23, 28, and so on. In each one of these, if you add the digits, they add up to a number that is a multiple of 5.

In other words, if X has a multiple that is one less than the base a number is expressed in, then a number is only divisible by X if its digits add up to a value that is itself divisible by X

Subtraction Tricks

Divisibility by 7 is one of the less commonly used and more awkward to understand tricks. using this method, we take one part of the number, and subtract a multiple of it from the other part of the number. In the case of divisibility by 7, we can take the "ones" column, multiply it by two, and subtract it from the rest of the number. If the resulting difference is divisible by seven, then the original number is as well. That pattern can be repeated on the resulting number until we get down to 7, -7, or 0.

For example, take the number 9268. We'll take the last digit, "8", double it, and subtract from the first three, "926". 926 - (2 × 8) = 910. Not sure? Repeat the process. 91 - (2 × 0) = 91, and 9 - (2 × 1) = 7. Seven is of course divisible by seven, so we know then that 9268 is as well.

This works because of a relationship between the digits, and a particular multiple of 7. First, consider our original number, 9268. We'll break that down into the two numbers we're working with, 926 and 8. Let's take two variables, A and B. we'll say that A equals 926 and B equals 8. In that case we can say:

9268 = 10A + B

In that case, if 9268 is divisible by 7, then 10A + B is as well. With that in mind we can say that if 10A + B is divisible by 7, then 20A + 2B is as well. All we're doing here is doubling the original number, so seven remains a factor.

At this point, we know that 20A + 2B has a factor of 7, but we don't know if either A or B does. We do however know that 21A would have a factor of 7, no matter what the value of A is. We know this because 7 is a factor of 21. With that in mind, we can say:

if 20A + 2B is divisible by 7, then 20A + 2B - 21A is also divisible by 7.

and then we can simplify it:

20A + 2B - 21A = -A + 2B

Whether the number is positive or negative does not affect its divisibility, so we can easily say that if -A + 2B is divisible by 7, then A - 2B is also. Recall that B is our rightmost digit, and A is the rest of the number. This is how this method of testing works.

We can apply this trick in other bases as well. An example of this would be for testing multiples of 5 in base 8 (octal) notation. Take the decimal number 190. In octal, this would be expressed as 276. The trick to divide by 5 in octal would be to take the last digit, "6" in this case, multiply it by three, and subtract it from the remainder of the number. We would have:

27 - 3×6 = 27 - 22 = 5

That may look wrong at first glance but remember that's octal notation, not decimal. If we expressed that statement in decimal, it would read "23 - 3×6 = 23 - 18 = 5".

This method can be used generically to define tricks for any number of factors. It works best for those that have a small multiple that is one away from a multiple of the base in which the number is expressed. Another example of this, in our more familiar decimal notation, would be in checking for multiples of 13. Using the same method, we can say that if a number is divisible by 13, then we can represent its rightmost digit with "B", and the remaining digits with "A", and say:

10A + B is divisible by 13
∴ 40A + 4B is divisible by 13
∴ 40A + 4B -39A is divisible by 13 (as 39 is also a multiple of 13)
∴ A + 4B is divisible by 13

So we can take the last digit of a number, quadruple it, and add it to the rest of the number. If the result is divisible by 13, then the rest of the number is as well. Having to multiply by 4 rather than 2 makes this a somewhat less convenient trick, but nonetheless a working one. For example, take the number 16042:

1604 + (2 × 4) = 1604 + 8 = 1612
161 + (2 × 4) = 161 + 8 = 169
16 + (9 × 4) = 16 + 36 = 52
5 + (2 × 4) = 5 + 8 = 13
Combinations of tricks

These tricks can also be combined. Division by six is an excellent examlpe of that. If the number's digits add up to a multiple of three, and if it's an even number, then the number is a multiple of six. This works of course because 2 and 3 are both factors of 6. A similar combination in hexadecimal would be testing for multiples of ten (or "A"). A number is divisible by A if it's an even number, and if its digits add up to a multiple of 5. This is because 2 and 5 are the two factors of A.

In Summary

In closing then, here is a summary of the tests outlined above, re-expressed in a way that can be applied in any numeric base.

If:

Then:

  1. X is divisible by Bn, where n is the number of 0's on the end of X
  2. if B is divisible by F, then X is divisible by F if the last digit of X is a multiple of F
  3. if Bn is divisible by F, then X is divisible by F if the last n digits of X form a multiple of F
  4. if F has a multiple that is one less than B, then X is divisible by F if the sum of the digits in X is divisible by F

You may notice that the second statement here is actually a subset of the third one. That is, if B is divisible by F, then Bn is as well. The only difference here is that in the first case, n can be as low as "1". I keep them separate because of the unique distinction of F actually being a factor of B, as opposed to simply sharing a common one.

< Older Blog - The Latest - Pick One - Show All - Newer Blog >