Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3

Question

I am trying to prove that $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 for all $k \in Z$.

I am not even sure what tags to use because I am not sure of right methods to use to solve this problem. I don't see how you could solve this with induction. Any tips on the general approach would be appreciated.

Answer 1

Let $k = a_0 + 10a_1 + 10^2a_2 + ... + 10^na_n$, this is a decimal representation where $a_i$ represents an individual digit.

Consider $k \pmod 3$.

Since $10^i \equiv 1^i = 1\pmod 3$,

$k \equiv a_0 + a_1 + ... + a_n \pmod 3$, and you're done.

Using induction is more unwieldy, and you'll still have to use modular arithmetic to do the inductive step (I think).