Let $a$ be a number written (in base 10) as $$a=a_0\cdot10^0+a_1\cdot10^1+a_2\cdot10^2+\cdots+a_n\cdot10^n$$ where $0\leq a_i <10$. Prove the following:

2 divides $a$ if and only if 2 divides $a_0$

4 divides $a$ if and only if 4 divides $a_0+2a_1$

8 divides $a$ if and only if 8 divides $a_0+2a_1+4a_2$

5 divides $a$ if and only if 5 divides $a_0$

9 divides $a$ if and only if 9 divides the sum $a_0+a_1+\cdots+a_n$ of its digits.

3 divides $a$ if and only if 3 divides the sum of its digits.

11 divides $a$ if and only if 11 divides $a_0-a_1+a_2-\cdots$.

I have played around with these and tried a few things, including modular arithmetic and odd/even arguments. I have a feeling that the same proof strategy can be used for all of these. What proof strategy is that?

Thank you.

  • $\begingroup$ Modular arithmetic? $\endgroup$ – Alexey Jan 14 '15 at 13:58
  • $\begingroup$ @Alexey I probably used the wrong terminology. I tried solving equations like $a_0+2a_1\equiv 0 \pmod{4}$ implies $a\equiv 0 \pmod{4}$ $\endgroup$ – Patrick Shambayati Jan 14 '15 at 14:03
  • $\begingroup$ I meant that your strategy is probably called "modular arithmetic." $\endgroup$ – Alexey Jan 14 '15 at 15:29

All of them can be proved by regrouping the terms and their factors.

For example, $a_0\cdot10^0+a_1\cdot10^1+a_2\cdot10^2+\cdots+a_n\cdot10^n$ can be written in the following formats using simple factorization: (dots represent the respective terms required, I hope you can understand.)

(i) $a_0+2(\cdots)$

(ii) $a_0+10a_1+100(\cdots)=a_0+2a_1+4(\cdots)$

(iii) $a_0+10a_1+100a_2+1000(\cdots)=a_0+2a_1+4a_2+4(\cdots)$

(iv) $a_0+5(\cdots)$

(v) $a_0+(a_1+9a_1)+(a_2+99a_2)+(a_3+999a_3)=a_0+a_1+a_2+\cdots+9(\cdots)=a_0+a_1+a_2+\cdots+3(\cdots)$

This is only a hint, you will have to fill in the $\cdots$.

I'm not sure about $11$, someone else could answer it.

  • $\begingroup$ 10^n = (-1)^(n+1) mod 11 $\endgroup$ – M.B. Jan 14 '15 at 14:26
  • $\begingroup$ @M.B.: Is it $(n+1)$? Shouldn't it be $n$? $\endgroup$ – user 170039 Jan 14 '15 at 14:31
  • 1
    $\begingroup$ Oh I see! So for (i), I would say $a=a_0+2(5a_1+50a_2+500a_3+\cdots)$. Then can I say the following? "thus, $a/2=a_0/2+5a_1+50a_2+500a_3+\cdots$ and $2|a$ iff $2|a_0$" $\endgroup$ – Patrick Shambayati Jan 14 '15 at 14:33
  • $\begingroup$ Yes, that's what I meant. @PatrickShambayati $\endgroup$ – ghosts_in_the_code Jan 14 '15 at 15:06
  • $\begingroup$ Thanks. If you were wondering, for 11 it's: $a=(a_0-a_1+a_2-\cdots) +11(a_1+9a_2+91a_3+909a_4+9091a_5+90909a_6+909091a_7+\cdots)$ $\endgroup$ – Patrick Shambayati Jan 14 '15 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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