|Re: An interesting challenge -- spoiler?|
Message #5 Posted by Dieter on 19 Nov 2011, 8:38 a.m.,
in response to message #4 by Marcus von Cube, Germany
You will easily get the idea if you look at the example of a, say, four-digit number.
This number will consist of the four digits abcd. It can be divided by 9 if abcd mod 9 = 0.
A number abcd can be written as
1000 a + 100 b + 10 c + d
We now want to evaluate
(1000 a + 100 b + 10 c + d) mod 9
= (999a + a + 99b + b + 9c + c + d) mod 9
Since 999, 99, 9 etc. are all integer multiples of 9, this simplifies to
(a + b + c + d) mod 9
In other words: in order to test whether a number can be divided by 9, simply check the sum of its digits. So if the remainder of the digit sum divided by 9 is zero, the number itself can be divided by 9 as well. This also means: if the remainder is 3 or 6, i.e. it can be divided by 3, the number itself is divisible by 3.
In other words:
If the digit sum is divisible by 9 resp. 3, so is the number itself.
n = 12345
sum of digits = 15
15 is not divisible by 9, but the remainder (6) is. Or: 15 can be divided by 3. So 12345 is divisible by 3 as well.
BTW, you can also continue with the digit sum of 15 which is 6 and judge the divisibility from this result. ;-)
Edited: 19 Nov 2011, 8:43 a.m.