# Proving $k$ is divisible by $3$ iff the sum of the digits of $k$ is divisible by 3 [duplicate]

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.

## marked as duplicate by user147263, Peter Taylor, Daniel Robert-Nicoud, Willie Wong, DarioApr 17 '15 at 12:40

• What is $10\mod 3$? – user223391 Apr 17 '15 at 5:30
• Is the hint from avid19 helping you? – Moti Apr 17 '15 at 5:38
• Yes, I see that I have to use modular arithmetic. – user3699546 Apr 17 '15 at 5:40

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.
• Would I have to prove that $10^i \cong 1^i = 1 (mod 3)$ or is this something you can assume and if so why? – user3699546 Apr 17 '15 at 6:06
• @user3699546 You can prove it very simply, start with $10 = 3*3 + 1\equiv 1 \pmod 3$. Then $10^i \equiv 1^i \pmod 3$ by the rules of modular exponentiation. Alternatively, you can apply binomial theorem to expand out $10^i = (3*3 + 1)^i$ and all the terms except the $1$ are multiples of $3$ leading you to the same conclusion. – Deepak Apr 17 '15 at 6:08