Sunday 17 November 2013

elementary number theory - If $3$ divides the decimal digit sum of $n$ then $3$ divides $n$ (casting out threes)




This is a trick I learnt in primary school, but never gave it much thought. Here's how I formulate it:
$$
n = \sum_{j=0}^{m} x_j 10^{m-j}
$$
is a decimal expansion of some integer $n$ such that
$$
\sum_{j=0}^{m} x_j = r
$$

such that $3|r$, then $3|n$. Or, $r= 3k$ and $n=3i$ with $k \neq i$. I thought about it for some time, but didn't get any intuition.


Answer



Hint. Take the difference
$$n-r = \sum_{j=0}^{m} x_j (10^{m-j}-1)$$
and note that $3$ (but also 9) divides $(10^{m-j}-1)$.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...