# How to Prove the divisibility rule for $3$

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

• @julien will both Modular and Conversely help me work this problem out? – Aj521 Mar 26 '13 at 1:10
• 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)$. – Julien 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

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

• Could you walk me through the process of getting this answer and understanding what is going on? – Aj521 Mar 26 '13 at 0:54
• @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
• I just had a student use this proof without citing it. I guess you could count this as an upvote? – the Hampster Dec 10 '18 at 1:07

$\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$. 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
• @fgp For sufficiency, you can expand the induction step and say "Assuming that it has been proven up to $3n$ that the divisibility condition is sufficient and necessary. We want to show that for $3n+1,3n+2$, the divisibility condition does not hold, but it does for $3n+3$." Then you can do them all in one, by using $m+i, 1\leq i\leq 3$ above (and $m+i-9$ and so on for the carries). – Arthur Feb 22 '15 at 9:45

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

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.

• You could say that, since $10 \equiv 1 \mod 3$, then $10^i \equiv 1 \mod 3$. – steven gregory Nov 2 '15 at 17:48

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)

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.

• 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
• en.wikipedia.org/wiki/Modular_arithmetic – Novice Oct 18 '13 at 16:52
• '|' means divides. – Novice Oct 18 '13 at 16:53

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

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

$$n=10^ka_k+\cdots+10a_1+a_0$$ and hence

$$n -\mbox{sum of its digits}=\left( 10^ka_k+\cdots+10a_1+a_0\right)-\left( a_k+\cdots+a_1+a_0\right)\\ =a_k(10^k-1)+\cdots+a_1(10-1)=a_k\cdot 99\ldots9+\cdots+a_1 \cdot 9 \\ =9\left( a_k\cdot 11\ldots1+\cdots+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$.

• 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
• How would you go about doing these same steps in the case of proving that $3|n$ if and only if $3|s(n)$, where $n = (a_k \times 10^k) + (a_{k-1} \times 10^{k-1}) + \cdots +(a_1 \times 10^1)+ (a_0 \times 10^0)$ and $s(n)=(a_k + a_{k-1}+ \cdots +a_1+a_0)$? @N.S. – Claire Dec 8 '18 at 20:25
• @Claire $$n -\mbox{sum of its digits}= 3\bigl(3\left( a_k\cdot 11\ldots1+\cdots+a_2\cdot 11+a_1 \right)\bigr)$$ – N. S. Dec 9 '18 at 18:03

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

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

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

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

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.

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

• Why the downvote? – Zubin Mukerjee Apr 19 '15 at 17:39
• 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 Apr 19 '15 at 17:51
• @ZubinMukerjee i know it has been more than three years, but what does the line above $a_0 a_1 a_2 ... a_{n-1}$ means? I'm not familiar with such notation. – user481197 Jan 13 '18 at 13:07
• I just found this comment: math.stackexchange.com/a/1309973/481197 I now know it. but is it necessary in this proof? – user481197 Jan 13 '18 at 13:13
• Hello @AbdukMalekAltawekji. In this case the overline is used to denote that the $a_0a_1a_2\cdots a_{n- 1}$ term denotes a number with $n$ digits, as opposed to a product. Normally when variables are written next to each other, it means they are multiplied together. In this case the overline is used to clarify that it's not $a_0 \cdot a_1 \cdot a_2 \cdots a_3$. In the other answer you linked, the overline is after a decimal point, and indicates a repeating decimal. – Zubin Mukerjee Jan 14 '18 at 1:38

This can be easily proven by "Digital Root" concept.

Digital root: A digit obtained by adding digits of number until a single digit is obtained.

All natural number is partitioned into 9 equivalence class by "Digital root".

Any number of Digital root 1 is represented by $1+9\times n$ any number of Digital root 2 is represented by $2+9\times n$ and so on.

(the reason for writing like this is: 9 is identity in the case of finding digital root)

So a number whose sum is 3. i.e., Digital root is 3 can be written as $3+9*i$. Which is divisible by 3.(It's clear from this representation).