Question: an integer n is divisible by 3 if and only if the sum of digits of n is divisible by 3. In other words, if n= a0+ 10 a1 +102 a2 +…+ 10k ak, then n is divisible by 3 if and only if a0+a1+a2+…+ak is divisible by 3.
Proof
lemma1
10^p - 1 = 9*10^(p-1) + 9*10^(p-2) + ... + 9*10 + 9
10^p - 1 = 3k
Hence, 3 | 10^p - 1 (3 divides 10^p - 1)
Let N = a0 + 10.a1 +10^2. a2 +…+ 10^n.an
and M = a0 + a1 + a2 +…+ an
If 3 | M, then M = 3q, say.
N - M = (a0 + 10.a1 +10^2. a2 +…+ 10^n.an) - (a0 + a1 + a2 +…+ an)
N - M = a1(10 - 1) + a2(10^2 - 1) + ... + an(10^n - 1)
Using lemma1,
N - M = a1.3k1 + a2.3k2 + ... + an.3kn = 3m, say.
N - 3q = 3m
N = 3s => 3 | N
Q.E.D.