Digital root (source code)

= Digital root
{title2=$\operatorname{dr}_b(n)$}

The <digital root> of a <nonnegative integer> in integer <radix> $b\ge2$ is the single <numerical digit> obtained by repeatedly taking its <digit sum>. For example, in <decimal representation>, $347\mapsto14\mapsto5$, while $999\mapsto27\mapsto9$.

The process terminates: if $n\ge b$, some nonzero digit occupies a position above the units, so $n=\sum_jd_jb^j>\sum_jd_j=s_b(n)$. The <positive integers> therefore decrease until a single <numerical digit> remains. Each step preserves the <integer congruence> class <modulo> $b-1$.

For positive inputs, every <digit sum> stays positive. The final digit lies in $1,\ldots,b-1$, rather than $0,\ldots,b-2$. Choosing the representative in this range gives
$$
\operatorname{dr}_b(n)=1+((n-1)\bmod(b-1))\qquad(n>0),
$$
with $\operatorname{dr}_b(0)=0$. This explains why a positive multiple of $9$ has decimal <digital root> $9$, not zero. The formula combines <modular arithmetic> with the positivity of the terminating representative.