1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.