Multiples of Three

1. Apr 18, 2010

Char. Limit

Why is it that if the sum of the digits of a number is divisible by three, the number itself is also divisible by three?

I've tried to do it, but I can't get anywhere. This is the best I have.

$$x=x_1+x_2\times10+x_3\times10^2+x_4\times10^3+...+x_i\times10^{i-1}$$

Which gives us the digits of x. So, why is it that if...

$$\frac{\sum_{i=1}^{n} x_i}{3} \in \mathbb{Z}$$

then...

$$\frac{x}{3} \in \mathbb{Z}$$

for an n-digit number x?

2. Apr 18, 2010

CRGreathouse

Because you're working in base 10, and 10 = 1 (mod 3). If you were working in base 8, then the sum of the digits would be divisible by 7 iff the original number was.

3. Apr 18, 2010

Dickfore

You should understand congruences:
$$\begin{array}{c} 1 \equiv 1 (\textrm{mod} \, 3) \\ 10 \equiv 1 (\textrm{mod} \, 3) \\ 10^{2} \equiv 1 (\textrm{mod} \, 3) \\ \cdots \\ 10^{n} \equiv 1 (\textrm{mod} \, 3) \end{array}$$
Multiplying each of the congruences by $$a_{n}$$, where $$a_{n}$$ is the nth digit from the right (the first one being labeled by $$a_{0}$$), and having in mind that:

$$x = \overline{a_{n} \cdots a_{1} a_{0}} = a_{n}*10^{n} + \cdots a_{1}*10 + a_{0}$$

so

$$x \equiv (a_{n} + \cdots + a_{1} + a_{0}) (\textrm{mod} \, 3)$$

Similarly, you can derive other criteria for divisibility.

4. Apr 18, 2010

Char. Limit

Thanks for the answers, I get it now. It makes total sense when you think about congruence, I guess.

5. Apr 19, 2010

Staff: Mentor

Actually it is more like number (written in base 10) is divisible by 9 if sum of digits is divisible by 9, 3 is just a side effect.

In general, this rule works for numbers in base n being divisible by n-1 if sum of digits is divisible by n-1.

6. Apr 19, 2010

Char. Limit

So the divisible-by-three rule would also work in base four, base seven, and any base 3n+1 then...

Thanks.