2
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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).

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user3699546 Apr 17 '15 at 6:06
  • $\begingroup$ @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. $\endgroup$ – Deepak Apr 17 '15 at 6:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.