# A number is divisible by 3 iff sum of its digits are divisible by 3

I was walking with my girlfriend other day, and I started telling her how Indian mathematics education is quite different and taught quite differently. One example I gave her was that they teaches you that a natural number is divisible by 3 if and only if the sum of its digits (in decimal representation) are also divisible by 3. Then I asked, “do you know why?” without knowing the answer. So both of us started thinking of ways to prove it. After a moment of thoughts, I came up with the proof idea for one direction: if the sum of digits of a natural number is divisible by 3, then the number is divisible by 3. Let’s formally prove this.

## Proof that if the sum of digits of a natural number in decimal representation is divisible by 3 then the number is also divisible by 3

Let n be a natural number with the decimal representation ${a}_{k}{a}_{k-1}\cdots {a}_{1}{a}_{0}$ where k is a non-negative integer and $\mathrm{\forall }0\le i\le k,0\le {a}_{i}\le 9$. Suppose the sum of digits is divisible by 3, which is to say  $\left(\sum _{i=0}^{k}{a}_{i}\right)mod3\equiv 0$

Then $n=\sum _{i=0}^{k}{a}_{i}\cdot {10}^{i}$. Because $10mod3\equiv 1$, it follows that $\mathrm{\forall }i\in {\mathbb{Z}}^{+},{10}^{i}mod3\equiv 1$ by properties of modular arithmetic. Thus ${a}_{i}\cdot {10}^{i}mod3\equiv \left({a}_{i}mod3\right)\cdot \left({10}^{i}mod3\right)mod3\equiv {a}_{i}mod3$. Hence $nmod3\equiv \left(\sum _{i=0}^{k}{a}_{i}\cdot {10}^{i}\right)mod3\equiv \left(\sum _{i=0}^{k}{a}_{i}\right)mod3$. By the supposition, $\left(\sum _{i=0}^{k}{a}_{i}\right)mod3\equiv 0$, and therefore $nmod3=0$ as desired. Q.E.D.

The proof for the other direction, however, quite troubled me to come up with. By supposing that the number is divisible by 3 doesn’t really give you any information about each digit. But this direction can be proved easily using the technique of proof by contradiction.

## Proof that if a natural number is divisible by 3, then the sum of its digits in decimal representation is also divisible by 3

Suppose not. Suppose there exists a natural number n that is divisible by 3 and the sum of its digits in decimal representation is not divisible by 3. That is to say if ${a}_{k}{a}_{k-1}\cdots {a}_{1}{a}_{0}$ is the decimal representation of n, then $\left(\sum _{i=0}^{k}{a}_{i}\right)mod3\ne 0$. It follows immediately that $n\equiv \sum _{i=0}^{k}{a}_{i}\cdot {10}^{i}$. But $nmod3=\left(\sum _{i=0}^{k}{a}_{i}\right)mod3$ using the same argument made for the previous proof (this result is derived without using the divisibility of the sum of digits in the previous proof). By supposition, $\left(\sum _{i=0}^{k}{a}_{i}\right)mod3\ne 0$ so $nmod3\ne 0$. Thus n is both divisible and not divisible by 3, which is a contradiction. Thus our supposition must be false and there is no natural number divisible by 3 and the sum of its digits in decimal representation is not divisible by 3, proving the statement. Q.E.D.