I'm working through an elementary number theory course right now and I think I've come up with a proof here but wanted some feedback on my logic.

Question: If the sum of the digits in base 10 is divisible by 9, then the number itself is divisible by 9.

Proof: Suppose that $9|d_1+d_2+...+d_n$ then $d_1+d_2+...+d_n=0\mod9$

Now consider $d_1(10^{n-1})+d_2(10^{n-2})+...+d_{(n-1)}(10^1)+d_n(10^0)$ Each power of $10$ is equivalent to $1\mod9$

therefor

$d_1(10^{n-1})+d_2(10^{n-2})+...+d_{(n-1)}(10^1)+d_n(10^0)=(1\mod9)(d_1+d_2+...d_n)$

$9|(d_1+d_2+...d_n)$ by our assumption, thus $9|(1\mod9)(d_1+d_2+...d_n)$

Thus we have shown that if 9 divides the sum of the digits in base 10, 9 divides the number itself.

The only question I really have is whether I'm jumping the gun on my assumption concerning the powers of 10 being $1\mod 9$. I think this is fair game here but not 100% confident. Thanks.


Yes, $\,{\rm mod}\ 9\!:\ \color{}{10\equiv 1}\,\Rightarrow\, \color{#c00}{10^n}\equiv 1^n \color{#c00}{\equiv 1},\,$ therefore

$\qquad\qquad\qquad\qquad\ \ d_n \color{#c00}{10^n} + d_1\color{#c00}{10} + d_0$
$\qquad\qquad\qquad \quad \equiv\,\ d_k +\cdots + d_1 + d_0\ \ $ by $ $ basic Congruence Rules.

More efficiently, we can observe that the decimal (radix $10)$ representation of an integer $N$ is a polynomial function $\,f(10)\,$ of the radix, with integer coefficients (digits) $\,d_i,\,$ i.e.

$$\begin{eqnarray} N\, =\, f(10) \!\!\!&&= d_n 10^n +\,\cdots+d_1 10 + d_0 \\ {\rm where}\ \ f(x) \!\!&&= d_n\, x^n\,+\,\cdots\,+d_1\, x\, + d_0\end{eqnarray}$$

Thus $\ {\rm mod}\ 9\!:\,\ \color{#c00}{10\equiv 1}\,\Rightarrow\, f(\color{#c00}{10})\equiv f(\color{#c00}{1}) = d_n+\cdots + d_1 \equiv\,$ sum of digits, which follows by applying the Polynomial Congruence Rule.

The proof works for any polynomial $\,f(x)\,$ with integer coefficients. As such, these tests for divisibility by the radix$\pm1$ (e.g. also casting out nines) may be viewed as special cases of the Polynomial Congruence Rule.