I’m an undergraduate student taking a Discrete Mathematics module. I have a proof question from a past year paper to prove that the digit sum, $s$ of a non-negative integer,$n$ satisfies the following result, $$s \equiv n\ (mod\ 9) $$.
I have approached it initially using a direct proof. A sketch of my proof would be deducing that $s-n$ reduces to $$ \sum_{i=0}^k d_{i}.(1-10^{i})$$, where $k$ is some non-negative integer and $d_{0},d_{1},...,d_{k}$ are the decimal digits of the number $n$. Afterwards, we need to prove that $9 \vert (1-10^{i})$ and by the linear combination property of integers, $9 \vert (s-n)$ which is then equivalent to saying $s \equiv n\ (mod\ 9) $. (By the way, $ \vert$, means "is a divisor of", in case this is not a universal notation)
My initial plan to prove this lemma: $9 \vert (1-10^{i})$ is by Mathematical induction, but it looks like this question is supposed to be simple due to the marks awarded, so Mathematical Induction might be an overkill.
Alternatively, I think a result I learnt from tutorial, which is that $9 \vert n \iff 9 \vert s$, might be useful here. However, I don’t know how I could link this result to modular arithmetic. I am also restricted to quoting results from the discrete mathematics textbook:Discrete Mathematics with applications by Susanna S. Epp, without proof, as well as tutorial results. Can someone share how this result might make my proof of the Lemma: $9 \vert (1-10^{i})$ simpler, or is there any other way of making this part simpler besides Mathematical Induction. Thanks.
You need to calculate $1-10^i \pmod 9$. Notice that you can reduce the number $10 \pmod 9$, since $a^i \equiv b^i$, if $a\equiv b$.
But $$10^i \equiv 1^i = 1 \pmod 9$$ so what you get is
$$1 - 10^i \equiv 1 - 1 = 0 \pmod 9$$ which is exactly what you want.