CACTUSPEAR.ORG PRESENTS

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 = ak·10k + ak-1·10k-1 + ... + a1·10 + a0 = ∑i=0k ai·10i

We 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.


cactuspear home
comments to comments at cactuspear dot org