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.
$\endgroup$ 23 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$Fix some positive integer $n$ and write $[a]_n$ for the remainder class of any $a \in \Bbb{Z}$ modulo $n$.
It isn't hard to prove (try it!) that $[a+b]_n = [a]_n + [b]_n$ and $[ab]_n = [a]_n[b]_n$ for every $a,b \in \Bbb{Z}$. A relation with this property is called a congruence.
In particular, this means that $[a^k]_n = [a]_n^k$ for every $a,k \in \Bbb{Z}$.
$\endgroup$ 1 $\begingroup$$$\begin{align}653854-(6+5+3+8+5+4)&=6\cdot99999+5\cdot9999+3\cdot999+8\cdot99+5\cdot9\\ &=(6\cdot11111+5\cdot1111+3\cdot111+8\cdot11+5)\cdot9. \end{align}$$
A number and the sum of its digits differ by a multiple of $9$.
$\endgroup$
