n = ak·10k + ak-1·10k-1 + ... + a1·10 + a0 = ∑i=0k ai·10iWe need to show that n ≡ ∑i ai mod 3. To do so, we will show that each term in the expansion of the sum is congruent to its coefficient ai. That is, for each i, ai·10i ≡ ai mod 3. Let's take a closer look at the general term ai·10i. We may rewrite it as ai(9+1)i. Each term in the binary expansion of the latter expression will be a multiple of 9 except the last, which is just 1. More formally, ai(9+1)i = ai[C(i,0)9i10 + C(i,1)9i-111 + ... + C(i,i-1)911i-1 + C(i,i)901i] = ai(9i + i·9i-1 + ... + i·9 + 1) = ai(9i + i·9i-1 + ... + i·9) + ai = 9ai(9i-1 + i·9i-2 + ... + i) + ai By reflexivity, we have ai·10i ≡ [9ai(9i-1 + i·9i-2 + ... + i) + ai] mod 3 We also know that 0 ≡ 9ai(9i-1 + i·9i-2 + ... + i) mod 3 Subtracting, we get our result: ai·10i ≡ ai mod 3. It follows that n = ∑ai·10i ≡ ∑ai mod 3.