If $3$ divides the decimal digit sum of $n$ then $3$ divides $n$ (casting out threes) [duplicate]

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.

marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Nov 29 '16 at 17:49

• Write, e.g., $234=2(99+1)+ 3(9+1)+4\cdot1 = (2\cdot 99+3\cdot 9) +(2+3+4)$. – David Mitra Oct 16 '16 at 9:17
• This is a special case of casting out nines - see the linked duplicate. Also you had "divides" in the wrong order: e.g. $n$ is even iff $2$ divides $n\$ (not $n$ divides $2)\$ – Bill Dubuque Nov 29 '16 at 17:49
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)$.
• OK, so it boils down to expanding the decimal term: $10^{m-j} = (1+9)^{m-j} = \sum_{i=0}^{m-j} 9^{i}$, then all terms but one are multiples of 3 and the first term is $x_j$ for all $j$, hence the sum. Thanks! – Alex Oct 16 '16 at 11:44