Why Multiples of Three are Divisible by 3

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

Start with an integer x, which can also be written thus...

$$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?

 

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

 

[Dickfore]

You should understand congruences:
$$\begin{array}{c}<br /> 1 \equiv 1 (\textrm{mod} \, 3) \\<br /> 10 \equiv 1 (\textrm{mod} \, 3) \\<br /> 10^{2} \equiv 1 (\textrm{mod} \, 3) \\<br /> \cdots \\<br /> 10^{n} \equiv 1 (\textrm{mod} \, 3)<br /> \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.

 

[Char. Limit]

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.

You should understand congruences:
$$\begin{array}{c}<br /> 1 \equiv 1 (mod 3) \\<br /> 10 \equiv 1 (mod 3) \\<br /> 10^{2} \equiv 1 (mod 3) \\<br /> \dotslow \\<br /> 10^{n} \equiv 1 (mod 3)<br /> \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} \dotslow a_{1} a_{0}} = a_{n}*10^{n} + \dotslow a_{1}*10 + a_0{}$$

so

$$x \equiv (a_{n} + \dotslow + a_{1} + a_{0}) (mod 3)$$

Similarly, you can derive other criteria for divisibility.

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

 

[Borek]

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.

 

[Char. Limit]

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

Thanks.