# Base 10 proof strategy

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.

• Modular arithmetic? – Alexey Jan 14 '15 at 13:58
• @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}$ – Patrick Shambayati Jan 14 '15 at 14:03
• I meant that your strategy is probably called "modular arithmetic." – 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.

• 10^n = (-1)^(n+1) mod 11 – M.B. Jan 14 '15 at 14:26
• @M.B.: Is it $(n+1)$? Shouldn't it be $n$? – user 170039 Jan 14 '15 at 14:31
• 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$" – Patrick Shambayati Jan 14 '15 at 14:33
• Yes, that's what I meant. @PatrickShambayati – ghosts_in_the_code Jan 14 '15 at 15:06
• 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)$ – Patrick Shambayati Jan 14 '15 at 22:29