Divisibility Rules for Bases other than $10$

Solution 1:

Claim 1:

The divisibility rule for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n+1$'. Let '$s$' denote the sum of digits of '$a$' expressed in base '$n+1$'. Now $n|a \iff n|s$. More generally, $a \equiv s \pmod{n}$.

Example:

Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $14$. $$611 = 3 \times 14^2 + 1 \times 14^1 + 9 \times 14^0 = (319)_{14}$$ where $(319)_{14}$ denotes that the decimal number $611$ expressed in base $14$. The sum of the digits $s = 3 + 1 + 9 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.

Proof:

The proof for this claim writes itself out. Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n+1$'. $$a = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0$$ Now, note that \begin{align} n+1 & \equiv 1 \pmod n\\ (n+1)^k & \equiv 1 \pmod n \\ a_k \times (n+1)^k & \equiv a_k \pmod n \end{align} \begin{align} a & = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0 \\ & \equiv (a_m + a_{m-1} \cdots + a_0) \pmod n\\ a & \equiv s \pmod n \end{align} Hence proved.

Claim 2: The divisibility rule for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n-1$'. Let '$s$' denote the alternating sum of digits of '$a$' expressed in base '$n-1$' i.e. if $a = (a_ma_{m-1} \ldots a_0)_{n-1}$, $s = a_0 - a_1 + a_2 - \cdots + (-1)^{m-1}a_{m-1} + (-1)^m a_m$. Now $n|a$ if and only $n|s$. More generally, $a \equiv s \pmod{n}$.

Example:

Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $12$. $$611 = 4 \times 12^2 + 2 \times 12^1 + B \times 12^0 = (42B)_{12}$$ where $(42B)_{14}$ denotes that the decimal number $611$ expressed in base $12$, $A$ stands for the tenth digit and $B$ stands for the eleventh digit. The alternating sum of the digits $s = B_{12} - 2 + 4 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.

Proof:

The proof for this claim writes itself out just like the one above. Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n-1$'. $$a = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0$$ Now, note that \begin{align} n-1 & \equiv (-1) \pmod n\\ (n-1)^k & \equiv (-1)^k \pmod n \\ a_k \times (n-1)^k & \equiv (-1)^k a_k \pmod n \end{align} \begin{align} a & = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0 \\ & \equiv ((-1)^m a_m + (-1)^{m-1} a_{m-1} \cdots + a_0) \pmod n\\ a & \equiv s \pmod n \end{align} Hence proved.

Pros and Cons:

The one obvious advantage of the above divisibility rules is that it is a generalized divisibility rule that can be applied for any '$n$'.

However, the major disadvantage in these divisibility rules is that if a number is given in decimal system we need to first express the number in a different base. Expressing it in base $n-1$ or $n+1$ may turn out to be more expensive. (We might as well try direct division by $n$ instead of this procedure!). However, if the number given is already expressed in base $n+1$ or $n-1$, then checking for divisibility becomes a trivial issue.

Solution 2:

The test for base-10 divisibility by 11 has a straightforward analogue in other bases. For example, in base 12, 756899 is divisible by 13 because 7+6+9 = 5+8+9. One can extend this to a case that doesn't arise in base 10 because 10+1 is prime: If $n$ is any factor of $b+1$, then one can test for divisibility by $n$ in base $b$ by forming the two alternate-digit sums and checking if they differ by a multiple of $n$. For example consider base 8. Is the number ${7166}_8$ divisible by 3? It is if and only if 7+6 and 1+6 differ by a multiple of 3; obviously, they do, so the answer is yes.

The tests for divisibility by 2 and 5 have analogues in non-prime bases. For example, in base 12, numbers are divisible by 6 if and only if they end in 0 or 6; divisible by 4 if and only if they end in 0, 4, or 8; by 3 if and only if they end in 0, 3, 6, or 9; and by 2 if and only if they in 0, 2, 4, 6, 8, or A. Similarly the test for divisibility by 10 has an obvious analogue. In general, if $n$ divides $b$, then a base-$b$ number $X$ is divisible by $n$ if and only if its last digit is divisible by $n$.

The test for divisibility by 3 has analogues in bases $n$ where $n-1$ is not prime; if $n-1$ is divisible by $k$, you can check for divisibility by $k$ by adding up the base-$n$ digits and checking if the sum is divisible by $k$. For example, consider 82A in base 11. The sum of these digits is 20, which is even, and is also a multiple of 5; both 2 and 5 divide 11-1=10, so 82A is a multiple of both 5 and 2. But the sum of the digits in 654 is 15, a multiple of 5 but not of 2, so 654 is a multiple of 5 but not of 2.