Originally Posted by

**topsquark** Note that

10 = 1 (mod 3)

100 = 10*10 = 1*1 (mod 3) = 1 (mod 3)

etc.

so that

10^n = 1 (mod 3)

and

a*10^n = a*1 (mod 3) = a (mod 3)

Now, any number in base 10 can be written as

(Sum, i = 1 to n)a_i*10^i = (Sum, i = 1 to n)a_i*1 (mod 3) = (Sum, i = 1 to n) a_i (mod 3)

which is simply the sum of the digits of the number.

But (Sum, i = 1 to n) a_i is divisible by 3 if and only if (Sum, i = 1 to n) a_i = 0 (mod 3), thus the number (Sum, i = 1 to n) a_i*10^i is divisible by 3 iff (Sum, i = 1 to n) a_i is divisible by 3.

-Dan