Interesting digits proof I recently started writing the programming practice questions in TopCoder, and one question is about Interesting Digits:

An digit $D$ in base $B$ is interesting if for all multiple $X$ of $D$ (in base $B$), the sum of all digits of $X$ is also a multiple of $D$. Given $B$, compute all interesting digit $D$ in base $B$ ( $1 < D < B$ ).

I used the brute-force method, and after checking out the solution to the question found that there was a much simpler way:

Suppose $X = a_0\cdot B^0 + a_1\cdot B^1 + a_2\cdot B^2 +\ldots$ is a multiple of $D$, i.e $X\equiv 0 \pmod D$.
If $B\equiv 1 \pmod D$ then $X\equiv a_0 + a_1 + a_2 + \ldots \pmod D$. So $\text{SumDigit}(X)\equiv X \pmod D \equiv 0 \pmod D$.
We see that if $B \equiv 1 \pmod D$ then $D$ is an interesting digit.

Now my problem is I can't see how "$B \equiv 1 \pmod D$ then D is an interesting digit."...Please help! I can't seem to understand it and I feel so stupid!!
 A: Suppose $B = m \mod D$, where $0 \leq m < D$.
@dtldarek's answer shows that if $m=1$, then $D$ is interesting.
To see the other direction, suppose $m \neq 1$.
Then we see that $1.B+ (D-m) = 0 \mod D$, but $1+D-m = -(m-1) \neq 0 \mod D$, hence $D$ is not interesting in this case.
It follows that $D$ is interesting iff $m=1$.
A: Congratulations, you have just invented the divisibility rule for $3$ and $9$! That is, as you may remember a number is divisible by $9$ if and only if the sum of its digits is divisible by $9$ (same with $3$). In fact $10 \equiv 1 \pmod 3$, and $10 \equiv 1 \pmod 9$. It is exactly as you said, $$\mathrm{SumDigit}(X) = X \pmod D.$$
In other words, a digit $D$ is interesting (in the sense of your question) if you can check divisibility by $D$ just by summing digits of any number in question.
The main reason why it works is because $1^n = 1$ for any $n$, so $B^n \equiv 1 \pmod D$ and thus for such special $D$s, in arithmetic modulo $D$, writing digits next to each other (that is preforming operation $\langle a,b\rangle \mapsto a\cdot B + b$) is equivalent to summing them,
$$ a\cdot B + b \equiv a \cdot 1 + b \equiv a + b \pmod D.$$
I hope it answers your question ;-)
