0

Could someone give me a more or less rigorous proof of the digital root formula?

I saw this question. It asks only about intuition and so, the answers there are not helpful for me to understand the formula. I guess I do not have the intuition.

Here is the formula:

$dg$ - digital root

$dg(x) = 0, if x is 0$

$dg(x) = 9, if x = 0 mod 9$

$dg(x) = x mod 9, otherwise$

While solving the problems on leetcode I was able to notice the pattern of the repetition of the digital root and devise the above algorithm. After that I checked that the algorithm is correct according to internet. But still I can not prove it to myself.

So far I was only able to understand that

$x mod 9 = (x_1 + ... + x_n) mod 9$, where $x_1, ..., x_n$ - the digits of $x$

and after that everywhere on internet they make a conclusion that the above formula was proven. But I do not understand why.

Ok, we proved the above statement, but that does not mean that for the number

$y = x_1 + ... + x_n$

holds that

$x mod 9 = y mod 9$

and even if it would hold, we would need to prove the same statement for the digits of $y$ and then for their sum and so on. And it seems impossible to do, so, I hope for another way.

some1 here
  • 161
  • Welcome to MSE. Please use MathJax to format math on this site. To begin with, enclose all math expressions (including numbers) in $ signs. For example, $x_1^2$ will give you $x_1^2$. You'll get a much better response if your posts are easy to read. – saulspatz Apr 14 '21 at 16:58
  • You agree that a number is equivalent to the sum of its digits $\mod 9$, correct? If so, then for the next number you should see that the same will hold, meaning that all of the sums of digits are equivalent $\mod 9$. – Stephen Donovan Apr 14 '21 at 17:08
  • @StephenDonovan, oh. Nice catch. Now it only remains to somehow prove that the number in the end even without taking the $mod 9$ from it will be less than 10. Is it easy to do? – some1 here Apr 14 '21 at 19:09
  • Well by definition we know the digital root must be less than $10$ because if it was greater than or equal to $10$ then it's at least a two-digit number, meaning we're not done yet and have to take another digit sum. Also I should mention we know we always get to a one-digit number because the series of sums is strictly decreasing while the numbers have $2$ or more digits. – Stephen Donovan Apr 14 '21 at 19:13
  • @StephenDonovan, how can we prove that it is strictly decreasing? I feel it intuitively, but I can not prove it mathematically. I can just consider a few examples, like 999 or 9999. And say that since those numbers with only 9 digits decrease after one step (999 becomes 27 and 9999 becomes 36), then those with other digits will decrease for sure, since their digits are even less. Does it make sense? – some1 here Apr 14 '21 at 19:21
  • @StephenDonovan, but what if I will take an integer with an infinite amount of 9 digits? 99999... . Then the next step will be 9*infinity which is not less than 999999... . Or the 99999... is not an integer? – some1 here Apr 14 '21 at 19:22
  • Well the issue with that is that $9999\ldots$, if it is a number, is not an integer so it's outside the domain of the function, and therefore not a consideration. We can consider integers of arbitrary size, but the size of any given integer is always finite. – Stephen Donovan Apr 14 '21 at 19:25
  • Let us continue this discussion in chat. – Stephen Donovan Apr 14 '21 at 19:25

0 Answers0