To quickly determine the remainder when dividing a large whole number by 3, simply add its digits. The sum has the same remainder as the number you started with. Repeat the process until only 1 digit remains.

Take the number 56,789, for example. If you add its digits, you get 35. Adding digits again, you get 8, which has a remainder of 2 when divided by 3. Indeed, 56,789 = 3 · 18,929 + 2.

We can think of 56,789 as the sum of 50,000, 6,000, 700, 80 and 9. We are asserting the somewhat surprising result that 50,000 has the same remainder as 5; 6,000 has the same remainder as 6; 700 the same remainder as 7; and 80 the same remainder as 8.

Furthermore, this is true for any number when divided by 3.

Proof: Let n be a number with k + 1 digits when written in decimal format:

n = a_{k}·10^{k} + a_{k-1}·10^{k-1} + ... + a_{1}·10 + a_{0} = ∑_{i=0}^{k} a_{i}·10^{i}

We need to show that n ≡ ∑_{i} a_{i} mod 3. To do so, we will show that each term in the expansion of the sum is congruent to its coefficient a_{i}. That is, for each i, a_{i}·10^{i} ≡ a_{i} mod 3.

Let's take a closer look at the general term a_{i}·10^{i}. We may rewrite it as a_{i}(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, a_{i}(9+1)^{i} = a_{i}[C(i,0)9^{i}1^{0} + C(i,1)9^{i-1}1^{1} + ... + C(i,i-1)9^{1}1^{i-1} + C(i,i)9^{0}1^{i}]

= a_{i}(9^{i} + i·9^{i-1} + ... + i·9 + 1) = a_{i}(9^{i} + i·9^{i-1} + ... + i·9) + a_{i} = 9a_{i}(9^{i-1} + i·9^{i-2} + ... + i) + a_{i}

By reflexivity, we have a_{i}·10^{i} ≡ [9a_{i}(9^{i-1} + i·9^{i-2} + ... + i) + a_{i}] mod 3

We also know that 0 ≡ 9a_{i}(9^{i-1} + i·9^{i-2} + ... + i) mod 3

Subtracting, we get our result: a_{i}·10^{i} ≡ a_{i} mod 3.

It follows that n = ∑a_{i}·10^{i} ≡ ∑a_{i} mod 3.