Sum of digits and divisibility by 3

It's a known math curiosity that when we take a decimal (base 10) number and add its digits together, if the sum is divisible by 3 without a remainder, then the number itself is also divisible by 3 without remainder. Example:

426 -> 4 + 2 + 6 = 12
12 (mod 3) = 0 (12 / 3 = 4)
426 (mod 3) = 0 (426 / 3 = 142)

This fact is actually quite simple to prove. Consider the breakdown of 426 to multiples of powers of 10:

426 = 4 * 100 + 2 * 10 + 6

Written another way:

426 = 4 * (99 + 1) + 2 * (9 + 1) + 6
    = (4 * 99 + 2 * 9) + (4 + 2 + 6)

This clearly shows that for 426 to be divisible by 3, (4 + 2 + 6) must be divisible for 3. If this isn't immediately obvious, recall that:

1. If X (mod N) = 0, then Y * X (mod N) = 0 for any X and Y
2. If X (mod N) = 0 and Y (mod N) = 0, then X + Y (mod N) = 0 for any X and Y

Since any power of 10 is 999..9 + 1 (with the appropriate amount of 9s), and the 999..9 part is always divisible by 3, what's left is the sum of the digits, which implies the divisibility by 3 of the number.

P.S.:

1. This theorem is, of course, an if and only if relation. IFF the sum of the digits is divisible by 3, the number is divisible by 3.
2. Another rule says that if the sum of the digits is divisible by 9, the number is divisible by 9. Just replace 3 by 9 in the proof above, and this becomes obvious (the key fact is that 999..9 is always divisible by 3 and by 9).