Divisibility Tests

Ok, I know I said the next post would be about finding prime numbers, but this is more related to the previous post. Sometimes, for very large numbers, it's hard to figure out what numbers divide into it evenly. Here are a few simple tests for determining factors.

A number is divisible by...

• 2 if the number is even (i.e. ends in 0, 2, 4, 6, or 8)
• 3 if the sum of its digits is divisible by 3 (e.g., the number 873 is divisible by 3 because 8 + 7 + 3 is 18 and 18 is divisible by 3)
• 4 if the last two digits of the number form a number that is divisible by 4 (e.g. the number 8748 is divisible by 4 becuase the last two digits form the number 48, which is divisible by 4)
• 5 if the number ends in 0 or 5
• 6 if the number passes the divisibility tests for 2 and 3 (because 2 x 3 = 6)
• 7 if...I'll explain this test in a minute, it's a bit complex.
• 8 if the last three digits of the number form a number that is divisible by 8 (similar to the test for 4).
• 9 if the sum of the digits forms a number that is divisible by 9 (similar to the test for 3)
• 10 if the number ends in 0.
• 11 if ...I'll explain this test in a moment, too.
• 12 if the number is divisible by 4 and 3 (because 4 x 3 is 12. Note that we can't say that a number is divisible by 12 if it is divisible by 6 and 2 (even though 6 x 2 = 12) becuase if a number is divisible by 6, it is already automatically divisible by 2 (since 6 itself is divisible by 2). For tests like this (we'll call them composite tests, we have to use two numbers that have no factors in common themselves.)

Ok, now on to the tests for 7 and 11.

Seven:

• Cut the last digit off of the number in question and double it.
• Subtract this value from the truncated number (formed in step 1).
• Repeat these steps on the NEW number until you reach a number for which you can easily determine divisibility by 7.
• EXAMPLE
• 876497
• Remove the last digit (7) and double it to get 14.
• Subtract 14 from 87649 (the original number without its last digit) to get 87635.
• REPEAT:
• Remove the last digit of this new number (5) and double it to get 10.
• Subtract 10 from 8763 to get 8753.
• REPEAT:
• Remove 3 from this new number and double it to get 6.
• Subtract 6 from 875 to get 869.
• REPEAT:
• Remove 9 and double it to get 18.
• Subtract 18 from 86 to get 68.
• Now, since 68 is small enough to divide easily by 7, we can tell right off that since 68 is not divisible by 7 neither is the original number 876497.

Now, you might wonder why we would want to use such a strange test, but if you think about it, doubling and subtracting is a sight easier than doing long division. So even though the process takes a few moments, it probably takes less time than doing the long division and uses only very simple operations.

ELEVEN:

• Starting with the first digit, add up every other digit in the number and record the sum.
• Starting with the second digit, add up every other digit in the number and record the sum.
• Subtract the smaller of these two sum from the larger.
• If the result is divisible by 11, so is the original number.
• EXAMPLE
• 872993789
• Beginning with the first 8, add up 8, 2, 9, 7 and 9 to get 35.
• Now, beginning with the 7, add up 7, 9, 3 and 8 to get 27.
• Subtract 27 from 35 to get 9.
• Since 9 is not divisible by 11, neither is the original number 872993789.

With this one it's pretty easy to see why it is less difficult to use the divisibility test than to divide by 11 using long division.

Now, these tests will only tell you if a number is divisible by one of these values. It will not tell you what the result is when you divide by that number. But as you can see in the case of 11, for example, it is useful to know whether a particularly large number can be divided or not before actually attempting a long division that will end in a remainder.

Another note: you can devise divisibility tests for numbers like 15 and 21 by using the divisiblity tests for their factors. To see if a number can be divided by 15, just verify that the tests for 3 and 5 worked.

Additionally: you can repeat the tests as needed. For example. if you add up all of the digits of a number to test for divisibility by 3, but the number is still to big, you can add up the digits of that number and see if its result is divisible by 3. If we started with a very large number, say 1872938874929, and we added up all of its digits, we'd get 77. Is this divisible by 3? I don't know, but 7+7 is 14, which is not divisible by 3. Therefore 77 is not divisible by 3, therefore the original number is not divisible by 3.

This turned out to be a bit less coherent than I wanted, but I hope it makes sense.