# Prove all base 10 positive integers are divisible by 3 if the sum of their digits is divisible by 3 [duplicate]

I came across a strange property of $3$ in base $10$; for all integers I have tried, the following rule seems to be true:

The integer '$n$' is divisible by $3$ if the sum of the digits of the integer are also divisible by three.

Is there a proof to show that this in fact is true? Or a counter example to disprove?

An example of the rule:

Suppose '$n$' = $123456789$.

Then $$1+2+3+4+5+6+7+8+9 = 45$$ $$4+5 = 9$$ $$9 \mod 3 = 0$$ Therefore

$$123456789 \mod 3 = 0$$

Afterword: For those of you who are wondering, I realized this rule while working on a database where every third row had a value I was wanted. What I wanted was a way to determine if a given row number '$n$' was divisible by $3$ without actually performing the function $n/3 = 0?$ and so far the rule I came up hasn't failed.

-

## marked as duplicate by rschwieb, MJD, Andrey Rekalo, Amzoti, ThomasAug 8 '13 at 14:54

It's true. The reason is that $10 = 1 + 3\cdot k$, and that means $10^m = 1 + 3\cdot q$ for all $m$. [Note: it also works with $9$ in place of $3$.] –  Daniel Fischer Aug 8 '13 at 14:13
For example, write $1251=1\cdot(999+1)+2\cdot(99+1)+5\cdot(9+1)+1=\underbrace{1\cdot999+2\cdot99+5 \cdot 9}_{\text{divisible by }3}+ (1+2+5+1)$. Generalize... –  David Mitra Aug 8 '13 at 14:13
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.