# Prove that $m \equiv S_m \pmod 3$?

I'm not very fluent in mathematical proofs. High School has, sadly, not taught me any kind of proof-theory. That's why I would like your help with my proof of

$$m \equiv S_m \pmod 3.$$

where $S_m$ is the digit sum of $m$ and $\wedge$ is a logical-AND.

I'm going to use the very little that I know: Mathematical induction.

Basis:

$$A(1): S_m = 1 \wedge m = 1$$

$$m \equiv S_m \pmod 3\quad \text{because}\quad 1 \equiv 1 \pmod 3$$

Inductive Step:

$$A(n)\colon m = n \land S_m = \sum_{k=0}^K m_k = (m_0 + m_1 + \ldots + m_K)$$

$$m \equiv S_m \pmod 3.$$

So then

$$A(n+1)\colon m = n+1 \wedge S_m = \sum\limits_{k=0}^{K'} m_k = (m_0 + m_1 + \ldots + m_{K'})$$

$$m \equiv S_m \pmod 3.$$

I'm having trouble at the step of $A(n+1)$ because I don't know how to actually prove that it's valid? Please note that $m_0, \ldots, m_M$ refers to the summation of the digits of the number $m$. I just didn't find any good documentation that showed how to depict that in mathematical terms. Feel free to correct!

-
You may want to explain your notation a bit more: what is $S_m$ and $\wedge$? –  Eric O. Korman Aug 22 '10 at 15:01
Crap! Edited, and I'll re-iterate here too: $S_m$ is the digit sum of m and $\wedge$ is simply a logical-AND. –  IAE Aug 22 '10 at 15:05
I am going to guess (and you should make this clear) that S_m is the sum of the digits of m. In that case, if you are inducting on m you should be splitting into cases depending on how many carries there are. Also, you need to escape the backslashes (with one more backslash) to get curly braces to work. –  Qiaochu Yuan Aug 22 '10 at 15:05
Logical AND never makes anything clearer; you should avoid it whenever you can. –  Qiaochu Yuan Aug 22 '10 at 15:06
@SoulBeaver: most logical symbols are difficult to parse quickly and make the task of reading mathematics unnecessarily laborious. Unless you are actually talking about mathematical logic, you should avoid them. You can find this advice coming from many expert mathematical writers, among them Knuth and Munkres. Depending on what flows better you could separate them with a comma or just write them on separate lines. –  Qiaochu Yuan Aug 22 '10 at 15:43

The reason this works is as follows:

$$10 = 9 + 1$$

modulo 3 this says that $10 = 1$.

Numbers like $3157$ really mean $3 \cdot 10^3 + 1 \cdot 10^2 + 5 \cdot 10 + 7$, so applying the previous congruence we get $3 \cdot 10^3 + 1 \cdot 10^2 + 5 \cdot 10 + 7 = 3 + 1 + 5 + 7$ modulo 3.

Now that we have a strong understanding of why the theorem is true let head toward a detailed proof.

Let us use the principle that all numbers can be written down in base 10, for example the sequence of digits $(3,6,8,4)$ represents the number $4863$ (and a technicality, the empty sequence represents $0$).

First let us define the interpretation from sequences to numbers as a recursive function:

\begin{align} \text{interp}() &= 0 \\ \text{interp}(ds,d) &= d + 10 \cdot \text{interp}(ds) \end{align}

\begin{align} \text{digitalroot}() &= 0 \\ \text{digitalroot}(ds,d) &= d + \text{digitalroot}(ds) \end{align}

We can now prove the theorem (that the interpretation of a number is equal to its digital root) by induction on the length of the number:

Base case $\text{interp}() = 0 = \text{digitalroot}()$.

Inductive case, assume that $\text{interp}(ds) = \text{digitalroot}(ds)$, we would like to now prove that $d + 10 \cdot \text{interp}(ds) = d + \text{digitalroot}(ds)$, cancelling d and reducing the 10 to a 1 we simply have the hypothesis, which is known to be true. That completes the proof.

-

The best way to get the result is that to remember that writing $m=a_n...a_1a_0$ in base 10 is actually a shorthand for $$m=a_0+a_1\cdot10+...+a_n\cdot 10^n.$$ Now it's enough to observe that $10^n\equiv1\bmod 3$ for all $n$ and thus $$m\equiv a_0+a_1+...+a_n \bmod 3.$$

-

I'm having a little trouble understanding your formatting/notation, but I am guessing that what you want to show is that $m = S_m$ (mod 3) where $S_m$ is the sum of the digits of the number $m$. In the inductive, step, it looks like you are saying that $S_{n+1} = S_n + 1$. This is not always true (e.g. it is true if $n = 23$ but not true if $n = 59$). So you should consider the two cases where the last digit is not a 9 and where the last digit is a 9. You'll easily see you get the same thing mod 3 and this will complete the proof.

-

HINT: It suffices to work $\rm\pmod 9. \;$ Put $\rm\; S_N :=$ the sum of the decimal digits of $\rm N$.

Notice $\rm\;N = 10\: n + r \;\Rightarrow\; S_N = S_n + r \;\Rightarrow\; N - S_N = n - S_n + 9 \: n$.

Hence $\rm\; N - S_N \equiv n - S_n \pmod 9$ -- the inductive step.

SIMPLER: For $\rm N = a_k 10^k + \;\cdots + 10\; a_1 + a_0 \;$ put $\rm\; P(N) = a_k X^k + \;\cdots+ a_1 \; x + a_0$.

FACTOR THEOREM $\rm\;\Rightarrow\; X-1|P(X)-P(1) \;\Rightarrow\; 9|P(10)-P(1) \;\:$ i.e. $\rm\; 9|N - S_N$.

So casting nines follows from the Factor Theorem purely by the polynomial form of radix notation.

Yet another example of the power of polynomials!

-