Note: The first part of this post deals with explaining why you can quickly test a number for divisibility by 9. If you just want to know quick divisibility tests for numbers 2 through 10 and don't care about the explanation for 9, just jump to bulleted list at the bottom of this post.
Divisibility by 9 by Long Division
Is a given number divisible by 9? To answer this question there are a couple of practical methods. One is to divide the number by 9. If the remainder is 0, the answer is yes. This works well for relatively small numbers, but can take a long time for long numbers. To illustrate, let's divide a nine digit number (123456789) by 9:
- 9 goes into 1 (1 dividend digit) 0 times; 9 * 0 = 0; 1 - 0 = 1.
- Bring down the 2. 9 goes into 12 (2 dividend digits) 1 time; 9 * 1 = 9; 12 - 9 = 3.
- Bring down the 3. 9 goes into 33 (3 dividend digits) 3 times; 9 * 3 = 27; 33 - 27 = 6.
- Bring down the 4. 9 goes into 64 (4 dividend digits) 7 times; 9 * 7 = 63; 64 - 63 = 1.
- Bring down the 5. 9 goes into 15 (5 dividend digits) 1 time; 9 * 1 = 9; 15 - 9 = 6.
- Bring down the 6. 9 goes into 66 (6 dividend digits) 7 times; 9 * 7 = 63; 66 - 63 = 3.
- Bring down the 7. 9 goes into 37 (7 dividend digits) 4 times; 9 * 4 = 36; 37 - 36 = 1.
- Bring down the 8. 9 goes into 18 (8 dividend digits) 2 times; 9 * 2 = 18; 18 - 18 = 0.
- Bring down the 9. 9 goes into 9 (9 dividend digits) 1 time; 9 * 1 = 9; 9 - 9 = 0.
- Thus 123456789 / 9 = 13717421 remainder 0.
Since the remainder is 0, we know 123456789 is divisible by 9. We also know the quotient is 13717421, which is irrelevant to the question "Is 123456789 divisible by 9?" When I did this by hand on paper, it took me about 35 seconds to write out all parts in normal long division form. It's not terribly complex, but it does involve three steps (estimation, multiplication and subtraction) per quotient digit for a total of 24 steps just to find out if the original number was divisible by 9.
Divisibility by 9 by Summing Digits
The other method, which I learned in junior high, only requires repeated addition of one digit numbers to a sum. Given the number, add all the digits together. If the sum of the digits is divisible by 9, the original number is also divisible by 9. Once again we will illustrate by testing the same nine digit number (123456789):
- 1 + 2 = 3.
- 3 + 3 = 6.
- 6 + 4 = 10.
- 10 + 5 = 15.
- 15 + 6 = 21.
- 21 + 7 = 28.
- 28 + 8 = 36.
- 36 + 9 = 45.
- 45 / 9 = 5 remainder 0.
Since the remainder is 0, we know 123456789 is divisible by 9. This time we didn't compute the irrelevant quotient. Even better, we were able to determine this fact with only 11 steps (eight additions, one estimation, one multiplication, and one subtraction). When I did this by hand on paper, it took me about 17 seconds to write out all parts.
But wait! This rule can be applied iteratively. That is to say, once we add up all the digits and come up with 45, we can do it again:
- 4 + 5 = 9.
- 9 is by definition divisible by 9.
We were able to trade three steps (the final estimation, multiplication and subtraction) for one addition.
Summing Digits Explained
Why does this work? By definition 0 and 9 are divisible by 9. Adding 9 to a number is the same as adding 10 and subtracting 1:
- 9 + 9 = 18, or
- 9 + 10 - 1 = 18.
As you can see, when we add nine to a number, we increase the ten's place by one at the same time we decrease the one's place by one. We're effectively taking one from the one's place to give to the ten's place. This is what keeps the sum of digits always divisible by nine:
- 18 + 10 - 1 = 27.
- 27 + 10 - 1 = 36.
- 36 + 10 - 1 = 45.
- 45 + 10 - 1 = 54.
- 54 + 10 - 1 = 63.
- 63 + 10 - 1 = 72.
- 72 + 10 - 1 = 81.
- 81 + 10 - 1 = 90.
Next we go from 90 to 99:
- 90 + 10 = 100, then
- 100 - 1 = 99.
Next we go from 99 to 108:
- 99 + 10 = 109, then
- 109 - 1 = 108.
Even though we've moved beyond two digits, and have had to do some borrowing with our subtraction for the first time, we've shown that the rule still holds.
Divisibility by 3 by Summing Digits & Other Shortcuts
Another trick I learned at the same time was how to quickly test for divisibility by 3. I say another trick, but it is actually the same trick! If you add all the digits of a number together and the sum is divisible by 3, the original number is also divisible by 3. And as with 9, you can repeat this process until you wind up with a single digit.
Why does this work? It works because 3 is a factor of 9. If there were other factors of 9 greater than 1, this trick would work with them as well. Unfortunately 3 is the only factor of 9, so other methods are required for other numbers:
- A number is divisible by 2 if it is even. In other words, if the last digit of the number is 0, 2, 4, 6 or 8, the number is divisible by 2. This works because we use 10 digits 0 through 9, and 2 is a prime factor of 10.
- A number is divisible by 3 if the sum of the digits of the number is divisible by 3. (Already stated above, but included here for completeness.)
- A number is divisible by 4 if the last two digits are divisible by 4. This works because there are 100 two digit numbers (the remainder of a number divided by 100) and 100 is divisible by 4.
- A number is divisible by 5 if the last digit is 0 or 5. This works because we use 10 digits 0 through 9, and 5 is a prime factor of 10.
- A number is divisible by 6 if it is divisible by both 2 and 3. This works because 2 and 3 are the prime factors of 6.
- Sadly, there is no comparable shortcut for testing for divisibility by 7 (because 7 is not a prime factor of 9 or 10).
- A number is divisible by 8 if the last three digits are divisible by 8. This works because there are 1000 three digit numbers (the remainder of a number divided by 1000) and 1000 is divisible by 8.
- A number is divisible by 9 if the sum of the digits of the number is divisible by 9. (Also stated above, also included here for completeness.)
- A number is divisible by 10 if the last digit of the number is 0.
You may have already known some or all of these shortcuts, and you can build more shortcuts from these components. They can be handy if you ever need to quickly determine if a larger number is divisible by a smaller number. Ultimately they work because we count in base 10 which utilizes a collection of 10 digits and the largest digit is 9.
Miscellaneous
Part 2 will explore how these observations extend to other bases and how we might usefully apply them to specific problems.
Edited on 9 Feb 2011 to hopefully clarify the long division and better organize the sections related to the two methods of testing for divisibility by 9. Thanks to Jonathan Mecham for his insights.
Go Top