Why does adding all the digits in a number up and checking whether the sum can be divided by three work?
For example, take 333:
Add 3+3+3 to get 9, which is a multiple of 3, therefore 333 must be a multiple of 3. The same is also true of multiples of 9.
How does it work?
A correlary question, why doesn’t this property apply to other numbers?
It does also apply to 2.
12 -> 1 + 2 = 3 -> 
It works for 9 as well.
My favorite has always been 11: add up alternating digits and the two sums should differ by a multiple of 11 (checkable by the same rule).
ex: 12345 * 11 = 135795
Sum 1: 1 + 5 + 9 = 15
Sum 2: 3 + 7 + 5 = 15
Difference: 0
Cool.
Why does this one work?
Because 10[sup]n[/sup] is one more than a multiple of three. Consider 123.
123 = 1100 + 210 + 3
= 1*(99+1) + 2*(9+1) + 3
= 199 + 11 + 29 + 21 + 3
= (199+ 29) + 1+2+3
= 9*(111 + 2) + 1+2+3
9(1*11 + 2) is a multiple of 3, so subtracting it will not affect whether the value is a multiple of 3. We are left with the sum of the digits.
1+2+3 is a multiple of 3, so 123 is a multiple of 3 also.
Why does it work?
Pretty easy really. I’ll try to explain in English rather than math-ese; I’m sure a prof will come along to clarify the notation. And from here on out we’re going to be talking strictly about integers, so I won’t mention that caveat again.
To say a number is divisible by 3 is really to say the remainder is zero when you divide it by 3.
Consider a 2-digit number whose digits are X & Y (i.e. written “XY”). The value is 10X+Y.
Whatever actual value it has, the remainder when divided by 3 is 0, 1, or 2.
Compare the value 10X + Y (the true value) with the value X+Y (the sum-of-digits value). i.e subtract X+Y from 10X+Y.
What’s the resulting difference? 9X. Is 9X disivible by 3? Yes, always, regardless of the value of X, becasue the 9 is divisible by 3. Or in other words, the remainder of 9X divided by 3 is zero for all values of X.
So you can remove 9X-worth of the value from the 10X+Y and still have the same divide-by-3 remainder. If the remainder was 0 before, it’s still 0 now. Or, if 10X+Y was divisible by 3, so is X+Y. Or in specifics, if 42 is divisible by 3, so is 4+2.
QED, at least for 2-digit numbers.
The same logic can be applied to 3 digit numbers too, and by induction to numbers of any length. If the sum is itself multi-digited, just add those digits together, and keep repeating the sum-of-digits process until you get to a single digit result. e.g. 3456789 -> 42 -> 6 is divisible by 3.
A similar method also works for determining if something is divisible by 9. Take a look at 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, etc. In each case add the digits (multiple times if necessary) and if they sum to 9, your original number is divisible by 9.
In number bases other than the traditional base ten we use, this same method still works, but for different values. It always works for the number one less than the base value. For example, in base eight, it works for seven. In base sixteen it works for fifteen.
And it’ll always work for the values which factor that (base minus one) value. In traditional base ten, nine is disivible by three and so it also works for three. In base eight, seven is prime and so it only works for seven. In base sixteen, fifteen is divisible by five and three, and so it works for five and three.
Integer math is fun that way.
The really interesting thing is that a division test can be created for any number n by listing the remainders when dividing n into bases of ten from 0 on. (n mod 1, n mod 10 n mod 100, n mod 1000, etc.) At some point the pattern will repeat itself. This is guaranteed to happen in less than n steps.
I’m sure that was perfectly clear, but I’ll do an example with the number 7 just in case.
7 mod 1 = 1 (We’ll call this R1)
7 mod 10 = 3 (We’ll call this R2)
7 mod 100 = 2 (We’ll call this R3)
7 mod 1000 = 6 (We’ll call this R4)
7 mod 10000 = 4 (We’ll call this R5)
7 mod 100000 = 5 (We’ll call this R6)
7 mod 1000000 = 1 (this is the beginning of the pattern repeating)
Now say we have a number m =D6 D5 D4 D3 D2 D1 (where D1, D2, etc are digits) and we want to check its divisibility by 7. If R1 * D1 + R2 * D2 + R3 * D3 + R4 * D4 + R5 * D5 + R6 * D6 is a multiple of 7 then m is a multiple of seven.
Lets look at 49. R1 * D1 + R2 * D2 = 1 * 9 + 3 * 4 = 21 a multiple of seven.
Now look at 654325: 15 + 32 + 23 + 64 + 45 + 56 = 91 = 7 * 14.
As you can see our sums get larger, to get around this we can shift values in our R series by seven to keep it more manageable. When we subtract 7 from the last three values of our R series we get: 1, 3, 2, -1, -3, -2. Using this series will keep our sum lower. It also tells us that all numbers in the form ABCABC are multiples of 7, which is kind of neat.
For numbers longer than 6 digits just start R series over when you get to its end until you run out of digits.
31415926535897932385 is a 20 digit number (too big to check in many calculators) that is a multiple of 7. Using R{1, 3, 2, -1, -3, -2} we get a sum of 56.
Other Notes:
I believe that I read that this method was created by Pascal.
Also most prime numbers have R series of length (p – 1)/2. However, some do not. 37 has an R series with just three members (R{1, 10, -11}) and 41 has an R series of 5. (R{1, 10, 18, 16, -4}) This is due to the fact that they are factors of 999 and 99999 respectively. Other primes that are factors of numbers of this type also have shorter than expected R series.
3 is a magic number. Yes it is.
Oops; sloppy thinking on my part there, what I should have said is that there is a similar rule for 2 - if the last digit is odd, it isn’t divisible by 2.
I’m going to hijack this thread by asking a similar math question. It is not as well known as the “3” is, but the easiest way to arrive at the lowest common denominator of a group of numbers is as follows. List the numbers vertically at the left edge of the paper. Factor out the 2s from those numbers, putting the 2 at the top of the list. To the right of the first column, you now have the numbers from the left which were not divisible by 2 and the dividends of the numbers that were. Now factor out the 3s and put the 3 at the top of the list. to the right of that column, you now have a third column which contains all the numbers in the second column that were not divisible by 3 plus the dividends of the numbers that were. Continue until there are only prime numbers in the list plus the factored numbers at the top of the list. Now multiply all the numbers and that is the LCD of the original numbers.
Example:
2 3 3(no 4) 5 (no 6) 7 (no 8, 9, or 10) 11
5 5 5 5 1 1 1
9 9 3 1 1 1 1
14 7 7 7 7 1 1
7 7 7 7 7 1 1
33 33 11 11 11 11 1
In the original series of numbers, there is no factor larger than 11, so the dividing ends. Multiply 2x3x3x5x7x11 and the LCD is 3960, which is quite large, but imagine trying to compute that LCD by any other method. It would take a while.
But why does this work?
It’s been a while since I’ve done that. To be more exact, the numbers you are factoring out are all prime (2, 3, 5, 7 and 11 in the above example), so you will have nothing but primes on top and should have nothing but 1s in the final vertical list. So you’re taking out all the primes, but sometimes, as in the number “9” you have to have the same prime number more than once on top.
[hijack - neat parlor trick!] This works well with a largish audience. Have one person write down a three digit number without showing it to you. Have him hand it over to the next person.
Next person repeats the number. E.g., if the number chosen was 572, the new number is 572572. HAve person #2 hand page over to person #3
Tell person #3 to devide the number by 7. Tell him not to worry, it’s divisible! You know it is! Now have it handed on…
Tell next person to divide number by 11(!). Tell him not to worry, …
Tell next person to divide it by 13(!!!). Still works!
Try to avoid letting on that you are now back to the very original number…
This works because ABCABC is actually just ABCx1001. And 1001 = 7x11x13.
[/hijack]
Dani
[QUOTE=Lance Turbo]
The really interesting thing is that a division test can be created for any number n by listing the remainders when dividing n into bases of ten from 0 on. (n mod 1, n mod 10 n mod 100, n mod 1000, etc.) At some point the pattern will repeat itself. This is guaranteed to happen in less than n steps.
I’m sure that was perfectly clear, but I’ll do an example with the number 7 just in case.
…QUOTE]
Love it!
I recall a list handed to me around 6th or 7th grade that gave tricks for remembering how to discover divisibility:
2: ends in an even digit
3: sum of digits is a multiple of 3
4: number represented by last two digits is a multiple of 4
5: ends in 0 or 5
6: even and divisible by 3
7: Double the last digit and subtract from number represented by remaining digits. Continue process with result until the final result is 7, 0 or -7 (or not). (Would LOVE to know how this one works in your system, Lance Turbo)
8: number represented by last three digits is divisible by 8
9: sum of (or sum of sum of, etc…) digits is 9
This can probably be proved with Lance Turbo’s general result, but the following is a test for divisibility by 7 that I learned long ago. Remove the last (units) digit from the number and double it. Then subtract this from the remaining number without the last digit (i.e., an n-1 digit number not an n digit number ending in 0). If the result is divisible by 7 (can iterate) then the original number is.
Example: 6328
632- 28 = 616
61 - 26 = 49 (obviously divisible but to illustrate a point continue)
4 - 29 = -14 (when you get a negative answer you must apply the
test to the absolute value since -1 - 24 = -9)
Roughly:
Start with an example like yours, say ABCDE * 11. That’s the same as ABCDE10 + ABCDE. If there are no carries in the addition, then the digits of ABCDE11 are:
A
A+B
B+C
C+D
D+E
E
And the alternating sums are:
A + (B+C) + (D+E)
(A+B) + (C+D) + E
which are equal. What if there was a carry in the addition? For example, say that C+D is more than 9. Then instead of (C+D) for that digit, it’s (C+D-10), and instead of (B+C) for the next highest digit, it’s (B+C+1). So:
A + (B+C+1) + (D+E) = A+B+C+D+E+1
(A+B) + (C+D-10) + E = A+B+C+D+E-10
which have a difference of 11.
That 7 trick is pretty cool. Here’s why it works.
We have a number n which is divisible by 7 so n = 7m.
Any n can be represented in terms of A and B like so n = 10A + B where B is the digit in the ones column and A is all the other columns divided by 10. The test is that if 10A + B is a multiple of seven then A – 2B will be a multiple of seven. (Subtract B, divide by ten, then subtract twice B.)
A can be represented in terms of B and another integer C like so: A = C + DB. Any A can be represented thusly, so we don’t lose generality. (C may be negative)
Now we have 10(C + DB) + B = 7m or 10C + (10D + 1)B = 7m. Both terms of this addition must be divisible by 7 so D=2 and we’ll let C = 7E (E is also an integer but may be negative). Substituting back into our equation for A we get A = 7E + 2B. (Also 7E = A – 2B)
We can substitute this back into our original number and get 10(7E + 2B) + B = 7m. Any multiple of seven can be constructed this way.
Now we perform the test ((10(7E + 2B) + B) – B)/10) – 2B
This simplifies to 7E which is clearly divisible by 7, and equals A – 2B from above.
Another miracle of clarity I’m sure.
The cool thing is that we can create a similar test for any odd number.
For 11: Take last digit off original number and subtract it from what remains.
1331 yields 133 – 1 = 132 which yields 13 – 2 = 11
For 19: Take last digit off original number and ADD it twice to what remains.
703 yields 70 + 6 = 76 which yields 7 + 12 = 19
For 131: Take last digit off original number and subtract it thirteen times from what remains.
31571 yields 3157 – 13 = 3144 which yields 314 – 52 = 262 which yields 26 – 26 = 0
I think you get the idea.