Suppose that we have a positive integer x and we write x= a0 + a1×10 + a2×102 + a3×103... + an×10n Since 10≡1 (mod 3), then for any positive integer m we have 10m ≡1m ≡1 (mod 3)
Therefore,
(a0 + a1×10 + a2×102 + a3×103... + an×10n) ≡ 1×(a0 + a1+ a2+a3... + an) (mod 3)
x≡(a0 + a1+ a2+a3... + an) (mod 3)
Therefore, the remainder when x is divisible by 3 is the same as the remainder when the sum of the digits is divisible by 3. The remainder is 0 if and only if 3 divides x.
We can also use this proof for the divisibility rule for 9 since 10≡1 (mod 9) as well.