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.

Example:

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. ;-)

Dieter

*Edited: 19 Nov 2011, 8:43 a.m. *