Many years ago, I learned an easy way to determine if a number (integer) is evenly divisible by 3: Just add up the digits and if the result is divisible by 3, so is the original number. For example, 12: 1 + 2 = 3, so 12 is evenly divisible by 3; 257: 2 + 5 + 7 = 14, then 1 + 4 = 5, so 257 is not evenly divisible by 3; but 255: 2 + 5 + 5 = 12 which is divisible by 3, so 255 is divisible by 3. The last two examples also point out that you can either stop after adding the digits of the original number or continue recursively until you get a single digit.
My question is, why does that work? And the related question: why doesn’t it work for any other number? For example, 12 is evenly divisible by 2, but 1 + 2 = 3, which is not evenly divisible by 2. 12 is also evenly divisible by 4, but 3 is not. 25 is evenly divisible by 5, but 2 + 5 = 7, which is not. 36 is evenly divisible by 6, but 3 + 6 = 9, which is not. Etc.
So what’s so special about the number 3 that this works only for that one number?
It works because 10, the base number, has a remainder of 1 when you divide it by 3. Since 10 has a remainder of 1, n x 10, or n x 10[sup]2[/sup], or n multiplied by any power of 10, has a remainder equal to n. Any number expressed in base 10 consists of multiples of powers of 10 – 672, for example, is 6 x 10[sup]2[/sup] + 7 x 10[sup]1[/sup] + 2 x 10[sup]0[/sup]. So the remainder of 672 when divided by 3 is just 6 + 7 + 2 = 15, but 15 is also divisible by 3 so the remainder is effectively 0. I.e. 672 is divisible by 3.
Seems to me that it might be a quirk of the base ten number system… something to do with the fact that after nine, you go to the next digit… does it work for nine as well?
The same trick also works for 9. I.e. 270549: 2 + 7 + 0 + 5 + 4 + 9 = 27, which is divisible by 9, therefore 270549 is divisible by 9. And for the same reason 3 works: 9 divided into 10[sup]x[/sup] leaves a remainder of one, the rest is identical to what Usram laid out.
So, let’s see… Let’s take the number 10011011000101101. The sum of the digits is 1001, and the sum of the digits of 1001 is 10, and the sum of the digits of 10 is 1, which is a multiple of 1. And sure enough, 10011011000101101 is a multiple of 1, too! Wow, it really works!
Thanks to all. The key to my getting a conceptual understanding of this was to experimentally confirm that it works for 7 in base 8. 14 in octal is 16, 1 + 6 = 7. And it also helped to notice along the way how I went about manually converting from base 10 to base 8.
