1
$\begingroup$

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!

  • 0
    The symbol \wedge, in particular, also has a completely different meaning in mathematics (the exterior product), and this gets confusing.2010-08-22

4 Answers 4

1

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!

3

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. $

3

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.

1

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.