# Number Theory - Proof of divisibility by $3$

Prove that for every positive integer $x$ of exactly four digits, if the sum of digits is divisible by $3$, then $x$ itself is divisible by 3 (i.e., consider $x = 6132$, the sum of digits of $x$ is $6+1+3+2 = 12$, which is divisible by 3, so $x$ is also divisible by $3$.)

How could I approach this proof? I'm not sure where I would even begin.

-
This is true for a number with any number of digits, and is a very well-known fact. As to where to begin to prove it yourself, do you know modular arithmetic? – Matt E Feb 25 '11 at 2:32
Yes i do that if x = y(mod3) then x and y divide 3? – Krysten Feb 25 '11 at 2:32
Here is a big hint: $6132=6000+100+30+2=6\cdot1000+1\cdot100+3\cdot10+2$. Why is this a hint? Well, what happens when you subtract $6+1+3+2$ from it? You get $6\cdot999+1\cdot99+3\cdot9+0$. – Andrés Caicedo Feb 25 '11 at 2:33
@Andres, thanks that helped a lot – Krysten Feb 25 '11 at 2:46
By the way Krysten, if $x=y\pmod{3}$, it means $3$ divides $x-y$, NOT that $x$ and $y$ divide $3$. For example, $5=2\pmod{3}$ since $3$ divides $5-2$, but neither $2$ nor $5$ divide $3$. – yunone Feb 25 '11 at 3:01

Suppose you have a number whose decimal digits are represented $a$, $b$, $c$, and $d$, so $x=abcd$.

In base $10$, this means $$x=abcd=a\cdot 10^3+b\cdot 10^2+c\cdot 10^1+d\cdot 10^0.$$ Try looking at $x$ modulo $3$, and remember that $10\equiv 1\pmod{3}$.

This concept is easily extended to an integer $x$ of any number of digits.

-
This concept is easily extended to an integer $x$ of any number of digits divided by any integer... – Quixotic Dec 2 '11 at 22:17

Actually, this is true for an integral number with any digits. The proof is quite easy. Let's denote the integral number by $\overline{a_n a_{n-1} \ldots a_1}$. If the sum of its digits $\sum_{i=1}^n{a_i}$ is divisible by 3, then $\sum_{i=1}^n{(1+\overline{9...9}_{i-1})*a_i}$ is too. Here $\overline{9...9}_{i-1}$ denotes the integer with $i-1$ 9's. But this second sum is just the original number $\overline{a_n a_{n-1} \ldots a_1}$ expanded.

-

It's due to radix representation being polynomial form in the radix, e.g. $\rm\ n = 4321 = p(10)\$ for $\rm\ p(x) = 4\: x^3 + 3\: x^2 + 2\: x + 1\:.\:$ Thus mod $\rm\:3\::\ 10\equiv 1\ \Rightarrow\ p(10)\equiv p(1)\ =\ \sigma(n) :=$ sum of digits. Aternatively one may simply put $\rm\ x = 10\$ in the $\:$ Factor Theorem $\rm\ \ x-1\ |\ p(x)-p(1)\:,\:$ hence $\rm\ 3\ |\ 9\ |\ p(10)-p(1) = n - \sigma(n)\:.\:$ This is a special case of casting out nines.

-