4

There was a question on SO on how to, in excel, sum all digits in a number until you are left with one single digit. The correct answer, in excel format, turns out to be =1+MOD(A1-1,9) which I wrote as $((n-1) \mod 9)+1$. I tried this it out with several numbers,

  • n=123 : $1+2+3 = 6$ and $((123-1) \mod 9)+1 = 6$
  • n=456 : $4+5+6 = 15, 1+5 = 6$ and $((465-1) \mod 9)+1 = 6$
  • n=8910 : $8+9+10 = 27, 2+7 = 9$ and $((8910-1) \mod 9)+1 = 9$

Now I try to understand the relationship between summing all the numbers and simply using the formula $((n-1) \mod 9)+1$. Why are these two always equal?

Community
  • 1
sowa
  • 165

2 Answers2

5

The sum of the digits in any number is congruent to that number modulo $9$. To see why it holds write the number $\overline{z...cba}$, as $a\cdot10^0 + b\cdot 10^1 +...$ and use the fact that the $10 \equiv 1 \pmod 9$. Repeating this step will not change the remainder modulo 9, so eventually we will get a number between $1$ and $9$, as $0$ is impossible.

On the other hand we get that $((n-1) \mod 9) + 1$ gives us the remainder of $n$ when divided by $9$. The trick when we first subtract $1$ and add it at the end ensures that we'll get a number between $1$ and $9$, rather than in the congruence class of $9$, which is from $0$ to $8$. In other words you calculate the remainder of $n-1$ modulo 9 and then you just add $1$ as the remainders between $n$ and $n-1$ differ by 1.

Stefan4024
  • 35,843
  • Once again I have problems with English syntax and I take long to write a solution. I wanted generalize to subtract not only $1$ but also any digit and comes out the same. And I suspect it may even be replaced $1$ by any other integer not only the first 8 digits. – Piquito May 17 '16 at 22:30
  • @Piquito if we replace 1 by any other integer than the formula will output numbers of the set ${k,k+1,...,k+8}$, which is not necessarily a one digit number. Actually we can see that only $k=1$ works – Stefan4024 May 17 '16 at 22:36
  • Hi Stefan: Look at this:(1) $439\to 439-5=434=48\cdot 9+2\to 2+5=7$. Now $4+3+9=16\to 1+6=7$.

    (2) $747\to747-8=739=82\cdot 9 +1\to 1+8=9$. Now $7+4+7=18\to 1+8=9$.

    You can verify the question with other values. Regards.

     – Piquito May 17 '16 at 22:55
  • @Piquito what about 39? We have $39 \to 3+9 = 12 \to 1+2 = 3$. On the other hand $((39-5) \mod 9) + 5 = 7 + 5 = 12$, but the results are different. Obviously they are congruent modulo 9 always, but this defeats the purpose of subtracting 1 at the beginning and adding it later, as we want to get the same number, not number that are congruent mod 9, but not necessarily same – Stefan4024 May 17 '16 at 23:00
  • I understand now what you say. However the residue must be of one digit and $1+2=3$. For a generalization it remains an easy additional detail. Finally let's get this. Thank you very much. – Piquito May 17 '16 at 23:10
  • @Piquito if we sum the digits until we get a digit then yes all integer serve the purpose. But as I've said the this becomes trivial, as what we do is similar to concluding that (2-1) + 1 is equal to 2 – Stefan4024 May 17 '16 at 23:13
0

(I saw this topic a long time ago, the formula needs to be proven. I use Google Translate from Vietnamese.)

Prove that the formula $P_{(s)} = (s - 1) \mod 9 + 1$ finds the sum of one digit of an integer greater than 0 with one or more digits.

Prove:

  • Let $A$ be the set of integers {$1,2,...,9$}.
  • Let $P_{(s)}$ be the sum of one digit of a multi-digit number.
  • Based on the formula $P_{(s)} = (s - 1) \mod 9 + 1$, $s > 0$, then $s - 1$ is always $s \ge 0$, so $P_{(s)} € A$.
  • Let $a1, a2, a3, ..., an$ be the digits in a number, the value of the set {$0,1,2,...,9$}.
  • Let $s$ be a 1 or more digit number.

Me has the general formula of $s$:

\begin{align} s & = a1*10^0 + a2*10^1 + a3*10^2 + ... + an*10^{n-1}\\ & = a1 + a2*10 + a3*10^2 + ... + an*10^{n-1}\\ & = a1 + a2 + a2*(10^1-1) + a3 + a3*(10^2-1) + ... + an + an*(10^{n-1}-1 )\\ & = a1 + a2 + a3 + ... + an + a2*9 + a3*99 + ... + an*(10^{n-1}-1 )\\ \end{align}

Let b be the value of the expression $a2*9 + a3*99 + ... + an*(10^{n-1}-1)$, based on the sign of divisibility by 9, b is always divisible by 9.

Let $C_{n}$ be the sum of n numbers, the values ​​obtained are respectively:

$C_{n}$ total value values
$C_{1}$ a1 $0 \to 1*10-1 = 9*1$
$C_{2}$ a1 + a2 $0 \to 2*10-2 = 9*2$
$C_{3}$ a1 + a2 + a3 $0 \to 3*10-3 = 9*3$
$C_{n}$ a1 + a2 + a3 + ... + an $0 \to n*10-n = 9*n$

\begin{align} Cₙ & = a1 + a2 + a3 + ... + an\\ & = a1 + a2*10 + a3*10^2 + ... + an*10^{n-1} - a2*9 - a3*99 - ... - an*(10^{n-1}-1)\\ & = s - b\\ \end{align}

Conclusion [1] :

  • when s loses b value, we get a sum of digits
  • [2] When n = 1, then $C_{n}$ € A , $s = C_{n}$, $P_{(s)} = (s - 1) \mod 9 + 1$ is always true.

With s:

\begin{align} s & = C_{n} + b\\ & = (C_{n})_{C_{n}} + b_{C_{n}} + b​\\ & = ((C_{n})_{C_{n}})_{C_{n}} + b_{(C_{n})_{C_{n}}} + b_{C_{n}} + b​\\ & = ...((C_{n})_{C_{n}})_{C_{n}} + b...((C_{n})_{C_{n}})_{C_{n}} + ... + b_{(C_{n})_{C_{n}}} + b_{C_{n}} + b​\\ \end{align}

Let $Z_{m}$ be the sum of $C_{n}$ the expression of the value s, to get [3] the value $Z_{m} € A$ then: \begin{align} s = b + bZ_{0} + bZ_{1} + bZ_{2} + ... + bZ_{m-1} + Z_{m}\\ \end{align} Let B be the value of the expression $b + bZ_{0} + bZ_{1} + bZ_{2} + ... + bZ_{m-1}$ then: $$s = Z_{m} + B​$$

Based on [1] :

\begin{align} P_{(s)} & = Z_{m} + B - B\\ & = Z_{m} + B \mod 9​\\ \end{align}

Based on [2] and [3] :

\begin{align} P_{(s)} & = (Z_{m}-1) \mod 9 + 1 + B \mod 9​\\ & = (Z_{m} + B - 1) \mod 9 + 1​\\ & = (s - 1) \mod 9 + 1​\\ \end{align}

Conclusion Thesis:

The formula $P_{(s)} = (s - 1) \mod 9 + 1$ finds the sum of one digit of an integer greater than 0 with one or more digits.

SanbiVN
  • 1