Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large numbers are multiples of three, because we can recursively apply this rule:

$$1212582439 \rightarrow 37 \rightarrow 10\rightarrow 1 \implies 3\not\mid 1212582439$$ $$124524 \rightarrow 18 \rightarrow 9 \implies 3\mid 124524$$

This works for as many numbers as I've tried. However, I'm not sure how this may be proven. Thus, my question is:

Given a positive integer $n$ and that $3\mid\text{(the sum of the digits of $n$)}$, how may we prove that $3\mid n$?

share|improve this question
2  
@julien will both Modular and Conversely help me work this problem out? –  Aj521 Mar 26 '13 at 1:10
6  
Hint: Notice that $10=3\times 3+1$. And write out the expansion in decimals. –  awllower Apr 28 '13 at 17:19
1  
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
2  
Furthermore, consider $10a+b=3(3a)+a+b$. Do the same to numbers greater than 100! –  awllower Apr 28 '13 at 17:23
5  
$$100a+10b+c=a+b+c+3(33a+3b)$$ –  Jyrki Lahtonen Apr 28 '13 at 17:24

16 Answers 16

up vote 7 down vote accepted

HINT: Suppose that you have a four-digit number $n$ that is written $abcd$. Then

$$\begin{align*} n&=10^3a+10^2b+10c+d\\ &=(999+1)a+(99+1)b+(9+1)c+d\\ &=(999a+99b+9c)+(a+b+c+d)\\ &=3(333a+33b+3c)+(a+b+c+d)\;, \end{align*}$$

so when you divide $n$ by $3$, you’ll get

$$333a+33b+3c+\frac{a+b+c+d}3\;.$$

The remainder is clearly going to come from the division $\frac{a+b+c+d}3$, since $333a+33b+3c$ is an integer.

Now generalize: make a similar argument for any number of digits, not just four. (If you know about congruences and modular arithmetic, you can do it very compactly.)

share|improve this answer
    
Could you walk me through the process of getting this answer and understanding what is going on? –  Aj521 Mar 26 '13 at 0:54
2  
@Aj521: The first line is just the meaning of base ten place-value notation, and the next three are just algebra. The rest is noticing that $$\frac{n}3=333a+33b+3c+\frac{a+b+c+d}3\;,$$ where $333a+33b+3c$ is an integer, so $\frac{n}3$ and $\frac{a+b+c+d}3$ must have the same remainder. For instance, $$\frac{1234}3=333\cdot1+33\cdot2+3\cdot3+\frac{10}3\;,$$ so the full quotient must be $333+66+9$ plus the integer part of $\frac{10}3$, and the remainder will all come from the $\frac{10}3$ part. –  Brian M. Scott Mar 26 '13 at 1:00
    
thank you alot. i understand the first line i get a little confused about A+b+c+d/3 come from? –  Aj521 Mar 26 '13 at 1:14
    
@Aj521: If $n=(999a+99b+9c)+(a+b+c+d)$, dividing both sides by $3$ gives you $$\frac{n}3=\frac{(999a+99b+9c)+(a+b+c+d)}3\;,$$ which is equal to $$\frac{999a+99b+9c}3+\frac{a+b+c+d)}3\;,$$ which, finally, is $$333a+33b+3c+\frac{a+b+c+d}3\;.$$ –  Brian M. Scott Mar 26 '13 at 1:17
    
Ok I see it now. thank you so much I can get back to this home work now. –  Aj521 Mar 26 '13 at 1:31

$\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.$

share|improve this answer

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

share|improve this answer
    
This sign "|" means "divides into"? –  Ovi Apr 28 '13 at 17:33
1  
@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

How about induction?

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.

share|improve this answer
2  
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
    
The induction methods is nice because it provides an insight into why this divisibility rule works. However, AFAICS, it only shows that the digit-sum being divisible by 3 is a necessary condition for the number being divisible by 3. I don't see how you'd get the sufficiency, though. –  fgp Feb 21 at 11:54

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

share|improve this answer

Yes, it is true. Let $$n = a_n a_{n-1} ... a_1 a_0 $$ the integer, where $0 \le a_i \le 9$ are its digits, that is $$ n = \sum_{i=0}^n a_i \cdot 10^i \ . $$ Since $10^i \equiv 1 \pmod 3$ ($10=3 \cdot 3 + 1$, $100 = 3 \cdot 33 + 1$ $1000 = 3 \cdot 333 + 1$ and so on), we can write $$ n = \sum_{i=0}^n a_i \cdot 10^i \equiv \sum_{i=0}^n a_i \pmod{3} $$ so $n$ is divisbile by 3, if and only if the sums of its digits is $$ (n \equiv 0 \pmod{3} \iff \sum_{i=0}^n a_i \equiv 0 \pmod{3} )$$ Q.E.D.

share|improve this answer

Let $a_k...a_0$ be the digits of $n$. Then

$$n=10^ka_k+...+10a_1+a_0$$ and hence

$$n -\mbox{sum of its digits}=\left( 10^ka_k+...+10a_1+a_0\right)-\left( a_k+...+a_1+a_0\right)\\ =a_k(10^k-1)+...+a_1(10-1)=a_k\cdot 99...9+...+a_1 \cdot 9 \\ =9\left( a_k\cdot 11...1+...+a_2\cdot 11+a_1 \right)$$

As $n -\mbox{sum of its digits}$ is a multiple of nine, it is a multiple of $3$.

share|improve this answer
    
i don't understand your last statement –  MyFavouritePhysicistIsNewtax Oct 18 '13 at 17:03
    
@MyFavouritePhysicistIsNewtax $n -\mbox{sum of its digits}=9 \cdot \mbox{junk}=3 \cdot (3 \cdot \mbox{junk})$ is a multiple of three. –  N. S. Oct 18 '13 at 17:48
    
@MyFavouritePhysicistIsNewtax Note that $n=\mbox{sum of digits}+ multiple of 3$. So both terms on RHS are multiple of $3$. –  N. S. Oct 18 '13 at 17:49

Divisibility by $3$ rule: $ 3\mid \overline {a_1a_2...a_n} \iff 3\mid (a_1+a_2+...+a_n)$, whereas $a_1,a_2,..a_n$ are digits in $\{0,1,2,...9\}$.

Proof: $\overline{a_1a_2...a_n} = a_1\cdot 10^{n-1} + a_2\cdot 10^{n-2} + ... + a_{n-1}\cdot 10 + a_n = a_1\cdot (9+1)^{n-1} + a_2\cdot (9+1)^{n-2} +...+ a_{n-1}\cdot (9+1) + a_n \cong a_1+a_2+...+a_n\pmod 3$.

Example: $3 \mid 4,722$ because $4+7+2+2 = 15$, and $1+5 = 6$ finally is a multiple of $3$. Check: $4,722 = 1,574 \times 3$.

share|improve this answer

Hint: take the number apart into digits. Each digit $d$ represents $d \cdot 10^n$ for some $n$. What is the remainder when you divide $10^n$ by $3$? (Think about $10^n-1$ what does it look like?)

share|improve this answer

Consider the following example:

Let us have a 3 digit number that can be divided by 3, ie xyz.

Therefore xyz=0 (mod3)

iff xyz=(100x)+(10y)+z=x+y+z=0(mod3)

Therefore x+y+z=0(mod 3), meaning that the sum of the digits is divisible by 3.

This is an if and only if statement.

You can generalize it to n digit numbers. The idea is to express the n digit numbers in powers of 10. Since powers of 10=1 (mod 3), the digit is divisible by 3 iff the sum is divisible by 3.

share|improve this answer
    
what is mod? I never heard of mod. –  MyFavouritePhysicistIsNewtax Oct 18 '13 at 16:48
    
That is modulo arithmetic, which deals with denominators. I actually abuse the notation of '=' here. We should use '$\equiv$'. We say that $a\equiv b(\mod\ n)$ iff $n|(a-b)$ or $n|(b-a)$ –  Novice Oct 18 '13 at 16:51
    
    
'|' means divides. –  Novice Oct 18 '13 at 16:53

Let abc be a 3 digit number divisible by 3.
Then: $$(100a+10b+c)|3=0$$ or $$(100|3)(a|3)+(10|3)(b|3)+(c|3)=0$$ Hence $$(a+b+c)|3=0$$

share|improve this answer
    
What | means? I'm just familiar with lcm and gcd –  MyFavouritePhysicistIsNewtax Oct 18 '13 at 16:51
    
@MyFavouritePhysicistIsNewtax | means "divides". 9|3 <=> 9 is a multiple of 3 –  Cruncher Feb 11 '14 at 20:32

Using Property$\#10$ of this ( indirect Proof),

as $10\equiv1\pmod9,10^r\equiv1^r\equiv1$ for integer $r\ge0$

$$\implies\sum_{r=0}^n10^ra_r\equiv\sum_{r=0}^na_r\pmod9$$

share|improve this answer

There's likely a more elegant proof, but you got me thinking about this, so here's what I came up with (this is for two digits, but it generalizes easily).

If some number 10a+b (for a,b integers) is divisible by three then there is some integer k such that 10a+b = 3k

This means that

10a+10b = 3k+9b and thus

10(a+b) = 3(k+3b)

so since 3 doesn't divide 10, it must divide a+b.

For the other direction:

If a+b = 3k, then

10a+b = 3k+9a = 3(k+3a)

share|improve this answer

Hint: Represent your number as $10^na_n+\cdots 10a_1+a_0$ where the $a_i's$ are the digit of your number. Now, note that the remained we get when we divide $10^k$ by $3$ is $1$.

share|improve this answer

Hint $\rm\ mod\ 3\!:\ 10\equiv 1\:\Rightarrow\: n = d_k 10^k+\cdots+d_1 10 + d_0 \equiv d_n+\cdots+d_1+d_0 = $ digit sum.

Or, $ $ let $\rm\:f = \,$ above polynomial (in $10),\:$ so $\rm\ n = f(10),\:$ and $\rm\ f(1) =\,$ digit sum of $\rm\,n.$

Factor Theorem $\rm\:\Rightarrow\: 3\mid 10\!-\!1\mid f(10)\!-f(1)\,$ $\Rightarrow$ $\rm\, f(10) = f(1) + 3k,\ $ so $\rm\ 3\mid f(10)\!\iff\!3\mid f(1)$

Remark $\ $ The same holds true if we replace $\,3\,$ by $\,9\,$ since, too, $\rm\:10\equiv 1\ \ (mod\ 9),\:$ i.e. $\rm\:9\mid 10\!-\!1.\ $ This leads to the casting out nines divisibility test, on which much has been written here.

share|improve this answer
    
Answer reposted after it was inexplicably deleted by a "moderator" after a merge. –  Bill Dubuque Apr 17 at 18:27
1  
Not sure why this was downvoted, +1 –  Zubin Mukerjee 2 days ago

For $n \in \mathbb{N}$, let $m = \overline{a_0a_1a_2\cdots a_{n-1}}$ be an $n$-digit natural number, where the $a_i$ are digits (natural numbers between $0$ and $9$, inclusive).

Then

$$ m = \displaystyle\sum\limits_{k=0}^{n-1}10^k \cdot a_k = a_0 + 10a_1 + 100a_2 + \cdots + 10^{n-1}a_{n-1}$$

Now consider the equation modulo $3$:

$$ m \equiv \displaystyle\sum\limits_{k=0}^{n-1} 10^k \cdot a_k \pmod{3}$$

$$ m \equiv \displaystyle\sum\limits_{k=0}^{n-1} (9+1)^k \cdot a_k \pmod{3}$$

Since $9 \equiv 0 \pmod{3}$, $9+1 \equiv 1 \pmod{3}$, and since $1^k \equiv 1 \pmod{3}$, we have

$$ m \equiv \displaystyle\sum\limits_{k=0}^{n-1} a_k \pmod{3}$$

This says that the remainder when $m$ is divided by $3$ is the same as the remainder of the sum of the digits of $m$ when that is divided by $3$.

share|improve this answer
    
Why the downvote? –  Zubin Mukerjee 2 days ago
1  
Probably the downvoter will not respond. In case you may not be aware, there are some users who, unfortunately, downvote for nonmathematical reasons (e.g to attempt to discourage answers to questions that they do not like, or to force deletion of questions they do not like, etc). This thread is a merge of many old questions and answers (see the comments to the question). –  Bill Dubuque 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.