Why do some divisibility rules work only in base 10?

Solution 1:

Two rules that work for any base $b$.

If $n$ divides $b-1$, then if the sum of the digits is a multiple of $n$ then the number is a multiple of $n$. (That's why the $3$ and $9$ rule work).

If the sum of the even place digits is a multiple of $b+1$ more or less than the sum of the odd place digits then the number is a multiple of $b+1$.

Proof outline:

Let $x = \sum c_i*b^i$ be a number is base $b$. Then the sum of the digits is $N=\sum c^i$. So $x - N = \sum c_i*(b^i - 1)$.

Each $b^i - 1 = (b-1)(b^{i-1}+b^{i-2} + .... + b + 1)$ so $x - N$ is a multiple of $b - 1$. So if $x$ is multiple of $b-1$ the sum of the digits is also a multiple of $b-1$.

Same thing if $x$ is a multiple of $n\mid b-1$.

Solution 2:

There are other rules for other bases.

To understand why the rule for $3$ works in base $10$, you need to write your number $x=d_n\times 10^n+\dots+d_1\times 10^1+d_0$ where the $d_i$ are the digits of $x$ in base $10$. You can notice that $10=3\times 3+1$, $10^2=3\times 33+1$, $10^n=3...3\times 3+1$ (where $3...3$ has $n-1$ digits equal to $3$). So $$\begin{align}x &=d_n\times (3...3\times 3+1)+\dots+d_1\times (3\times 3+1)+d_0 \\ &= (d_n\times 3...3 + \dots+d_1\times 3)\times 3 +d_n+\dots+d_1+d_0\end{align}$$

As you can see, the first term is divisible by $3$, so $x$ is divisible by $3$ if and only if $d_n+\dots+d_1+d_0$ is divisible by $3$. So the reason that this rule works is the fact that the rest of the division of a power of $10$ by $3$ is $1$.

In base $5$, the same rule applies with $2$ (because the powers of $5$ are odd). For example, in base $5$, $12$ is not divisible by $2$ ($1+2=3$ is not divisible by $2$) but $13$ and $431$ are.

To find rules like this by yourself for a base $b$ and a divisor $d$, you need to study how the powers of $b$ behave when divided by $d$.

Solution 3:

The reason why you can simply sum the digits of a number to test for divisibility by 3 is because for all integers $n \ge 0$:

$$10^n \equiv 1 \pmod 3$$

To see why this is true, we know that $10^1 \equiv 1 \pmod 3$

Thus:

$$ 10^n = 10*10*10 \cdots\\ \hspace{2.1cm} \equiv 1*1*1\cdots \pmod 3\\ \hspace{0.1cm} \equiv 1 \pmod 3\\ $$

From this we can see that for an integer $a_{n} a_{n-1} ...a_1$ in base 10 , $3 \mid a_{n} a_{n-1} ...a_1$ if and only if:

$$ \sum_{i=1}^{n} a_i \equiv 0 \pmod 3 $$

We can generalise this for any base, if $n$ is a digit in base $b$ such that:

$$ 10_b \equiv 1 \pmod n $$

Then for all integers $k \ge 0$:

$$ 10_b^k \equiv 1 \pmod n $$

There are divisibility rules for base 2.

For example, a binary number $a_{n} a_{n-1} ...a_1$ where $a_i$ is either $1$ or $0$, then $a_{n} a_{n-1} ...a_1$ is divisible by 3 if and only if:

$$ \sum_{i=1}^{\lfloor n/2 \rfloor} a_{2i} - \sum_{j=0}^{\lfloor n/2 \rfloor} a_{2j+1} \equiv 0 \pmod 3 $$

This means that $a_{n} a_{n-1} \cdots a_1$ is divisible by 3 if and only if the difference of the sum of the digits in the even positions and the sum of the digits in the odd positions is divisible by 3.

This applies in general as such for any base $b$ and a number $a_{n} a_{n-1} ...a_1$ in base $b$:

$$ (b+1) \mid a_{n-1} a_{n-2} ...a_1 $$

if and only if:

$$ \sum_{i=1}^{\lfloor n/2 \rfloor} a_{2i} - \sum_{j=0}^{\lfloor n/2 \rfloor} a_{2j+1} \equiv 0 \pmod {b+1} $$

To see why this is also true, we know that:

$$ b \equiv -1 \pmod {b+1} $$

Thus:

$$ b^2 \equiv 1 \pmod {b+1} $$

Thus for all integers $i \ge 0$:

$$ b^{2i+1} \equiv -1 \pmod {b+1} \space and \space \space b^{2i} \equiv 1 \pmod {b+1} $$

From this, $a_{n} a_{n-1} ...a_1$ is divisible by $b+1$ in base $b$ if an only if:

$$ a_1 + a_2 - a_3 + a_4 - \cdots + (-1)^{n-1}*a_n \equiv 0 \pmod {b+1} $$

which is equalvalent to:

$$ \sum_{i=1}^{\lfloor n/2 \rfloor} a_{2i} - \sum_{j=0}^{\lfloor n/2 \rfloor} a_{2j+1} \equiv 0 \pmod {b+1} $$

There might be 1 or 2 errors here (my first time using latex), feel free to point out.

Solution 4:

There are general rules for all bases.

One such rule that I've stumbled across is described on everything2.

For any integer base B greater than 2, the multiples of the number B-1, when represented in base B will always have the sum of the digits be a multiple of B-1. If B-1 is a square number (4,9,16,...) then the square root of B-1 will also have this property.