Looking for a theorem talking about the remainder when a number is divided by 9

Question

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.

Answer 1

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.

I don't think this is quite in the answers already given.

---

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

Answer 2

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.

Answer 3

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.\begin{equation} 10^n = 1+ 9\times \sum_{j=0}^{n-1} 10^j. \quad (1)\end{equation} 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.