# Looking for a theorem talking about the remainder when a number is divided by 9 [duplicate]

I have come across an interesting property of the number 9, which some people call it casting out nines.

This is the property: If any number is divisible by 9, then you can keep adding the digits until you get a 9. For example 9117 is divisible by 9, because 9+1+1+7=18, then from the 18 we can see that 1+8=9. But 9113 is not divisible by 9, because 9+1+1+3=14, and then from the 14 we deduce 1+4=5 which is the remainder when this number, 9113, is divided by 9.

My question is: Is there a theorem that summarises this concept? If the theorem exists, then what is its proof?

Thanks in anticipation.

## marked as duplicate by Bill Dubuque 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(); } ); }); }); Feb 6 '17 at 21:51

• @NeedForHelp What is different about this question is that it is asking about a method for determining the remainder of a number divisible by 9. – Namaste Feb 6 '17 at 21:06
• @NeedForHelp, understand the question. I am looking for a theorem and a proof. Provision of a link is also an answer. Provided the link is relevant. – Patrick Chidzalo Feb 6 '17 at 21:06

It is essentially an extension of the rule that a number is divisible by 9 if and only if the digits in the base ten representation add up to a number divisible by 9. You can prove that the digits of a number have to add up to a multiple of 9 by using the fact that every power of 10 is congruent to 1 modulo 9, viz.$$10^n = 1+ 9\times \sum_{j=0}^{n-1} 10^j. \quad (1)$$ Hence you have for any natural number $d=\sum_{j=0}^n d_j 10^j$, we have that $$d \cong l \mod 9$$ if and only if $$\sum_{j=0}^n d_j 10^j \cong l\mod 9$$ if and only if $$\sum_{j=0}^n d_j 1^j =\sum_{j=0}^n d_j\cong l \mod 9,$$ where we used (1) to get to the last line. Now use the fact that $\sum_{j=0}^n d_j 10^j > \sum_{j=0}^n d_j > 0$ and the result should be clear.

It helps to view this in the framework of modular arithmetic and congruence classes.

Define the relation: $$x\cong y\iff x-y=9k,\;k\in \mathbb{Z}$$ or in english, x and y differ by a multiple of $9$.

Then rewriting any number as the sum of a bunch of coefficients between $0$ and $9$ times a power of 10 (in other words, in base ten) and reducing modulo 9 gives the desired result.

Since that's wordy, here is your example in this framework. $$9117=9*10^3+1*10^2+1*10+7$$ Now we reduce modulo 9: $$9*10^3+10^2+10+7\cong 9+1+1+7\cong 18\cong 0$$ Since 9 goes into $1000$ 111 times with a remainder of 1, 9 goes into 100 11 times with a remainder of 1, and 9 goes into 10 once with a remainder of 1.

Finally, $18\cong 0$ since $18=2*9$, or taking $k=2$ in our definition.

There is nothing deeper going on here than noticing that powers of 10 can be reduced to 1 modulo 9, and being congruent to 0 modulo a number is the same as being divisible by that number.

The basic idea here is that $10\equiv 1\bmod 9$, which means that $10^n\equiv 1^n\equiv 1\bmod 9$. (see also comment at end)

This means that $$\sum_{r=0}^Na_r10^r\equiv \sum_{r=0}^Na_r \bmod 9$$because all the powers of $10$ reduce to $1$. If you were writing numbers in base $13$ you'd likewise be able to case out twelves, for example.

This works because reducing modulo $9$ is a homomorphism when applied to the additive group of integers