# Divisibility Rules for Bases other than $10$

I still remember the feeling, when I learned that a number is divisible by $3$, if the digit sum is divisible by $3$. The general way to get these rules for the regular decimal system is asked/answered here: Divisibility rules and congruences. Now I wonder, what divisibility rules an alien with $12$ (or $42$) fingers would come up with?

So let $n=\sum_k c_k b^k$ be the representation with base $b$. Looking at some examples shows indicate that $n$ is divisible by $b-1$, if $\sum_k c_k$ is. This seems to be a poor man's extension to the decimal divisibility by $9$ rule.

The answer to the above mentioned question, says that "One needn't memorize motley exotic divisibility tests. ". Motley exotic divisibility tests are very welcome here!

-
I don't think there any general tests other than minor variations on the method I describe there, viz. modulo the divisor, (Horner) evaluate the radix polynomial (or a convenient scaling or rearrangement of it). Every divisibility test I've seen can be viewed as a special case of this. That was the point of my answer there. –  Bill Dubuque May 23 '12 at 15:17
I am reminded yet again of an anecdote told by one of my professors: one time, an engineer came to his office very excited, because he had come up with a very easy general divisibility test. He pointed out that checking divisibility by 10 was very easy, because you only have to look at the last digit and see if it is zero or not. So his method was: to test whether $n$ is divisible by $b\gt 1$, write $n$ in base $b$ and check the last digit: if it is $0$, then $n$ is divisible by $b$; if not, then $n$ is not divisible by $b$. –  Arturo Magidin May 23 '12 at 18:19
@ArturoMagidin I thought about to exclude the engineer case in the body of the question. –  draks ... May 23 '12 at 18:24
@BillDubuque as you've kindly offered in a comment below, I would be also very happy if could explain this a little further. –  draks ... May 24 '12 at 8:16

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.

-
Thanks, great answer! –  draks ... May 23 '12 at 21:22
@draks This is a just a special case of the universal method that I described in the answer you linked to - see my comment to your question. If that was not clear to you then I would have been happy to explain further. The special cases are much easier to understand (and remember!) when viewed from this more general perspective. –  Bill Dubuque May 23 '12 at 23:44

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.

-
Thanks a lot.  –  draks ... May 23 '12 at 21:23
I think I have more to say about this. For example, on the way home I noticed that there is a not-too-awful test for divisibility by 7 in base 9. Consider ${228072482}_9$. Divide the digits into groups of three and sum the groups mod 7: 2+0+4=6; 2+7+8=17=3; 8+2+2=12=5. Then calculate 6·4+3·2+5 = 35. This is a multiple of 7, so the original number was also a multiple of 7. I will try to write up the general method in more detail later, or perhaps you can infer it from what Bill wrote above. –  MJD May 23 '12 at 21:51
Now it get's motley... –  draks ... May 24 '12 at 8:14
Are you still working on the more general method? I would really be interested... –  draks ... Jun 9 '12 at 15:35