remainder when divided by 3

To quickly determine the remainder when dividing a large whole number by 3, one may 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 modulo 3 as does 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₁·10 + a₀ = ∑_i=0^k a_i·10ⁱ

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ⁱ ≡ a_i mod 3.

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

= a_i(9ⁱ + i·9^i-1 + ... + i·9 + 1) = a_i(9ⁱ + 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ⁱ ≡ [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ⁱ ≡ a_i mod 3.

It follows that n = ∑a_i·10ⁱ ≡ ∑a_i mod 3.