# 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

Then

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