# divisibility by (n-1) in base n

I Just found out that if I want to check if a number in base $n$ is divisible by $n-1$, I just need to sum all the digits, again and again, until I get to a single character, and if this number is $n-1$, then this number is divisible by $n-1$.

For example, 45 in base 10 is divisible by 9, because the digits 4 + 5 = 9.

Why this happens?

I'm trying to prove it for base 16, and can't seem to get it right.

Say $x = d_m\cdot n^m+d_{m-1}\cdot n^{m-1}+...+d_0$ where $d_i$ denote the digits. We know that $x$ is divisible by $n-1$ if and only if $x\equiv 0\pmod{n-1}$. Observe that modulo $n-1$ we have $$x=d_m\cdot n^m+d_{m-1}\cdot n^{m-1}+...+d_0\equiv d_m+...+d_0\pmod{n-1}$$ since $n\equiv 1\pmod{n-1}$.
The argument shows that $x$ is divisible by $n-1$ if and only if the sum $d_m+...+d_0$, i.e. the sum of the digits of $x$ in base $n$, is divisible by $n-1$.
Edit : If the sum is $n-1$ we are done. If not you can repeat the argument by writing the sum as above.
Edit 2 : You can easily deduce other divisibility rules by the same method. For example if $n$ is divisible by $p$, then $x=d_m\cdot n^m+d_{m-1}\cdot n^{m-1}+...+d_0\equiv d_0\pmod{p}$ since $n\equiv 0\pmod p$. This is a generalization of the well-known divisibility by $2$ (respectively by $5$) rule in base $10$ : a number is divisible by $2$ (respectively by $5$) if and only if the last digit is divisible by $2$ (respectively by $5$). It may amuse you to deduce the divisibility rule for $n+1$.