# How to prove the divisibility rule for $3\,$ [casting out threes]

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? Mar 26, 2013 at 1:10
• Hint: Notice that $10=3\times 3+1$. And write out the expansion in decimals. Apr 28, 2013 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)$. Apr 28, 2013 at 17:21
• Furthermore, consider $10a+b=3(3a)+a+b$. Do the same to numbers greater than 100! Apr 28, 2013 at 17:23
• $$100a+10b+c=a+b+c+3(33a+3b)$$ Apr 28, 2013 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? Mar 26, 2013 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. Mar 26, 2013 at 1:00
• thank you alot. i understand the first line i get a little confused about A+b+c+d/3 come from? Mar 26, 2013 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\;.$$ Mar 26, 2013 at 1:17
• I just had a student use this proof without citing it. I guess you could count this as an upvote? Dec 10, 2018 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, 2013 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, 2013 at 17:34
• Oh ok thank you very much
– Ovi
Apr 28, 2013 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, 2013 at 17:41
• +1 for calling me an enlightened reader (and it being a good answer, I suppose). :) Apr 28, 2013 at 20:19
• This has a sort of induction-within-induction thing with the part talking about higher digits. Apr 28, 2013 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. Apr 28, 2013 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). Feb 22, 2015 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$. Nov 2, 2015 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)

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 Oct 18, 2013 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. Oct 18, 2013 at 17:48
• @MyFavouritePhysicistIsNewtax Note that $n=\mbox{sum of digits}+ multiple of 3$. So both terms on RHS are multiple of $3$. Oct 18, 2013 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. Dec 8, 2018 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)$$ Dec 9, 2018 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?)

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. Oct 18, 2013 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)$ Oct 18, 2013 at 16:51
• en.wikipedia.org/wiki/Modular_arithmetic Oct 18, 2013 at 16:52
• '|' means divides. Oct 18, 2013 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$$

• What | means? I'm just familiar with lcm and gcd Oct 18, 2013 at 16:51
• @MyFavouritePhysicistIsNewtax | means "divides". 9|3 <=> 9 is a multiple of 3 Feb 11, 2014 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$.

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? Apr 19, 2015 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). Apr 19, 2015 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, 2018 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, 2018 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. Jan 14, 2018 at 1:38

Since you tagged it let's use a little algebra to help clarify the essence of the matter.

\!\!\begin{align}\rm\ {\bf Hint}\ \ \ mod\ 3\!:\,\ \color{#C00}{10\equiv 1}\:\Rightarrow\ &\rm \overbrace{\rm n = d_k \color{#C00}{10}^k+\cdots+d_1 \color{#C00}{10} + d_0}^{\textstyle \text{\rm n\, in radix \,10\, (decimal)}} \equiv\, f(10) \\[.2em] &\rm \ \ \equiv\ d_k\,\color{#C00}1^k \:\!+\cdots +\ d_1\,\color{#C00}1\:\!+d_0\equiv\, f(1)\\[.2em] &\ \ \equiv\ \text{digit sum of \,\rm n}\end{align}

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.

The key point is that radix representation is a polynomial function of the radix, and polynomials (being compositions of sums and products) are compatible with modular arithmetic, i.e. $$\rm \bmod m\!:\ a\equiv b\Rightarrow f(a)\equiv f(b),\,$$ see the Polynomial Congruence Rule.

Note also that such modular "casting" methods are more powerful than classical divisibility tests like $$\,7\mid 10b+a\iff 7\mid b-2a\,$$ because the modular methods yield further info (the remainder), which allow us to perform perform further arithmetic on these values (e.g. to help check computations). See also the universal divisibility test.

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