# Divisibility by 3? [duplicate]

How do you prove that a number is divisible by 3 iff the sum of its digits is divisible by 3? Please avoid using the modulus or any other operations or advanced terminology from number theory because I have never taken that class.

-

## marked as duplicate by MJD, Amzoti, user1337, Thomas Andrews, Daniel RustAug 8 '13 at 15:02

Hint: Notice that $10=3\times 3+1$. And write out the expansion in decimals. –  awllower Apr 28 '13 at 17:19
It works for $3$ as $10\equiv 1$ mod $3$, as well as for $9$, as $10\equiv 1$ mod $9$. Do you know modular arithmetic? Otherwise, you can do that with $10^n-1=(10-1)(10^{n-1}+\ldots+1)$. –  1015 Apr 28 '13 at 17:21
So 10/3=3+.3333...? –  Ovi Apr 28 '13 at 17:21
Furthermore, consider $10a+b=3(3a)+a+b$. Do the same to numbers greater than 100! –  awllower Apr 28 '13 at 17:23
$$100a+10b+c=a+b+c+3(33a+3b)$$ –  Jyrki Lahtonen Apr 28 '13 at 17:24

$\begin{eqnarray} \rm{\bf Hint}\ \ &&\rm3\ \ divides\ \ a\! +\! 10\,b\! +\! 100\, c\! +\! 1000\,d\! + \cdots\\ \iff &&\rm 3\ \ divides\ \ a\! +\! b\! +\! c\! +\! d\! +\! \cdots +\color{#c00}9\,b\! +\! \color{#c00}{99}\,c\! +\! \color{#c00}{999}\,d\! + \cdots\\ \iff &&\rm3\ \ divides\ \ a\! +\! b\! +\! c\! +\! d + \cdots\ \ by\ \ 3\ \ divides\ \ \color{#c00}{9,\ 99,\ 999,\,\ldots}\end{eqnarray}$

Above we used that $\rm\ n + 3m\$ is divisible by $\rm\,3\iff n\:$ is divisible by $\,3.$

-
+1 Very nice: all but only what we need here! (Despite the fact the OP pleaded for "non-modular" arguments, it sure seemed to "take"! $\checkmark$) –  amWhy Apr 28 '13 at 17:45

$1$. First prove that $3 \mid 10^n - 1$ (By noting that, $10^n - 1 = (10-1)(10^{n-1} + 10^{n-2} + \cdots + 1)$).

$2$. Now any number can be written in decimal expansion as $$a = a_n 10^n + a_{n-1} 10^{n-1} + \cdots + a_1 10^1 + a_0$$

$3$. Note that $a_k 10^k = a_k + a_k (10^k-1)$. Hence, $$a = \overbrace{(a_n + a_{n-1} + \cdots + a_0)}^{b} + \underbrace{\left(a_n (10^n-1) + a_{n-1} (10^{n-1}-1) + \cdots + a_1 (10^1-1) \right)}_{c}$$

$4$. We have $a=b+c$ and $3 \mid c$. Now conclude that $3 \mid a \iff 3 \mid b$.

-
This sign "|" means "divides into"? –  Ovi Apr 28 '13 at 17:33
@Ovi $a \mid b$ means $a$ divides $b$, i.e., $b = k \times a$, where $k \in \mathbb{Z}$. For instance, $7 \mid 56$, since $7$ divides $56$. –  user17762 Apr 28 '13 at 17:34
Oh ok thank you very much –  Ovi Apr 28 '13 at 17:35

It is obviously true for the one-digit numbers $3, 6$ and $9$, so we have our base case (really, just the case $3$ is all it takes, but I like to be on the safe side when it comes to induction).

Now, let's say that we have a number divisible by $3$, and let's call it $n$. We can also assume that the sum of the digits of $n$ is divisible by $3$. I want to show that the sum of digits of $n+3$ is also divisible by $3$. If that is the case, then we are done, for the induction principle takes care of any case for us from there.

The sum of the digits of $n$ is some number, let's call it $m$, and this number is assumed to be divisible by $3$. Now, if we're lucky, the sum of digits in $n+3$ is just $m+3$, and by lucky I mean there is no carry involved. So, if there is no carry involved in adding $3$ to $n$, then we are done.

If there is a carry, however, then let's pretend for a second that the last digit of $n$ can surpass $9$. Were that the case, the sum of digits of $n+3$ would really be $m+3$. This is sadly not the case, but what really happens when we do the carry? We subtract $10$ from the $1$-digit, and add $1$ to the $10$-digit. This will have the net effect on the sum of digits that we subtract $9$, so in that case the sum of digits in $n+3$ is $m+3-9 = m-6$, which is still divisible by $3$, so there is no problem!

"Hold on there, not so fast", you say. "What if adding $1$ to the $10$-s digit makes a carry happen there?" Well, my enlightened reader, in that case the same argument as in the paragraph above would apply, only moved one space to the left in the digits of $n$. The net effect: the sum of digits of $n+3$ is $m-6-9 = m-15$, still divisible by $3$. If there is a carry from the hundreds-digit, then we will subtract another $9$ for a total of $m-24$. And so on. You will never make a carry like that take $m+3$ out of divisible-by-three-space. And this concludes the proof.

-
Thanks, induction is always nice. –  Ovi Apr 28 '13 at 17:41
+1 for calling me an enlightened reader (and it being a good answer, I suppose). :) –  Chris Apr 28 '13 at 20:19
This has a sort of induction-within-induction thing with the part talking about higher digits. –  AJMansfield Apr 28 '13 at 21:26
@AJMansfield I guess you could see it as induction. I wouldn't see it like that, though. I just see it as pointing out that each successive carry lowers the sum of digits by $9$, and therefore, no matter how many we perform, we will still end up with something divisible by three. In my opinion induction would possibly be a tool to achieve this, e.g. "Assume that carrying from some digit lowers the digit-sum by $9$. I will prove that the same goes for the digit to the left. By induction it therefore goes for all of the carries." There is no "stepping" necessary for that part, however. –  Arthur Apr 28 '13 at 22:22

More generally, a number and the sum of its digits both leave the same remainder on division by $3$. For example: $245$ $\mapsto 2+4+5=11$ $\mapsto1+1=2$, so the remainder when $245$ is divided by $3$ is $2$.

If you know modular arithmetic, this is straightforward: \begin{align} 245 & = 2\cdot10^2 +4\cdot10+5 \\[8pt] & \equiv 2\cdot1^2 + 4\cdot1 + 5 \pmod 3 \\[8pt] & = 2+4+5 \\[8pt] & = \text{sum of digits.} \end{align}

The point is that $10$ is congruent to $1$ when the modulus is $3$, since the remainder when dividing $10$ by $3$ is $1$, and so powers of $10$ are congruent to powers of $1$, and powers of $1$ are just $1$.

-