Proof 3

This proof is basically about a simple statement I learned in Middle-School about numbers divisible by 3. I was in the shower the other day (as cliche as it gets) and I thought of the statement, and wondered about a proof for it. By the time I was ready, a simple one had framed in my head. It’s probably out there, but I thought I’d share it nonetheless.

Claim : Given a number $m = a_{n} a_{n - 1} . . a_{0} \in ℤ$ , $∋ (m) m o d (3) = 0$ , we have that, $(\sum_{i = 1}^{i = n + 1} a_{i}) m o d (3) = 0$

Proof : Well, first lets just understand what we’re saying. We are saying that an integer is divisible by 3, iff, the sum of its digits are divisble by 3. This is useless if the number is between $[0, 9]$ , but becomes very useful when the number is large, and we are testing divisibility.

Before we write down the main proof, let’s make a small observation which is the backbone of the proof :

Lemma : $(10^{k}) m o d (3) = 1$ , $\forall k \in ℕ$

This is easy to see. This happens because :

$(10^{k}) m o d (3) = (10) m o d (3) * (10) m o d (3) . . . * (10) m o d (3)$ ( $k$ -times) = $1 * 1 . . . * 1 = 1$

So, now that we have this statement, let’s begin writing our main-proof :

To begin, let’s write down what we want : $(m) m o d (3) = 0$

So, let’s start reducing and re-writing this :

$≅ (a_{n} a_{n - 1} . . a_{0}) m o d (3) = 0$

$≅ (10^{n} a_{n} + 10^{n - 1} a_{n - 1} + . . + 10 a_{1} + a_{0}) m o d (3) = 0$

$≅ ((10^{n} a_{n}) m o d (3) + . . + (a_{0}) m o d (3)) = 0$

$≅ ((10^{n}) m o d (3) (a_{n}) m o d (3) + . . (a_{0}) m o d (3)) = 0$

$≅ 1 * (a_{n}) m o d (3) + . . + (a_{0}) m o d (3) = 0$ (Using the Lemma)

$≅ (a_{n}) m o d (3) + . . + (a_{0}) m o d (3) = 0$

$≅ (a_{n} + . . + a_{0}) m o d (3) = 0$

$≅ (\sum_{i = 1}^{i = n + 1} a_{i}) m o d (3) = 0$

Q.E.D.

So, there you have it. A simple proof, and one that I think is quite intuitive.