Divisibility Rules for Bases other than $10$

Question

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
– Bill Dubuque, Commented May 23, 2012 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 > 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
– Arturo Magidin, Commented May 23, 2012 at 18:19
@ArturoMagidin I thought about to exclude the engineer case in the body of the question. — draks ...
– draks ..., Commented May 23, 2012 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 ...
– draks ..., Commented May 24, 2012 at 8:16

user17762 · Accepted Answer · 2012-05-23 16:56:34Z

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 ⟺ n | s$ . More generally, $a \equiv s (\mod 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_{m} a_{m - 1} \dots 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} + \dots + a_{0}

Now, note that

\begin{aligned} n + 1 & \equiv 1 (\mod n) \\ (n + 1)^{k} & \equiv 1 (\mod n) \\ a_{k} \times (n + 1)^{k} & \equiv a_{k} (\mod n) \end{aligned}

\begin{aligned} a & = a_{m} \times (n + 1)^{m} + a_{m - 1} \times (n + 1)^{m - 1} + \dots + a_{0} \\ \equiv (a_{m} + a_{m - 1} \dots + a_{0}) (\mod n) \\ a & \equiv s (\mod n) \end{aligned}

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_{m} a_{m - 1} \dots a_{0})_{n - 1}$ , $s = a_{0} - a_{1} + a_{2} - \dots + (- 1)^{m - 1} a_{m - 1} + (- 1)^{m} a_{m}$ . Now $n | a$ if and only $n | s$ . More generally, $a \equiv s (\mod 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} = (42 B)_{12}

where

(42 B)_{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_{m} a_{m - 1} \dots 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} + \dots + a_{0}

Now, note that

\begin{aligned} n - 1 & \equiv (- 1) (\mod n) \\ (n - 1)^{k} & \equiv (- 1)^{k} (\mod n) \\ a_{k} \times (n - 1)^{k} & \equiv (- 1)^{k} a_{k} (\mod n) \end{aligned}

\begin{aligned} a & = a_{m} \times (n - 1)^{m} + a_{m - 1} \times (n - 1)^{m - 1} + \dots + a_{0} \\ \equiv ((- 1)^{m} a_{m} + (- 1)^{m - 1} a_{m - 1} \dots + a_{0}) (\mod n) \\ a & \equiv s (\mod n) \end{aligned}

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.

@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
– Bill Dubuque, Commented May 23, 2012 at 23:44

MJD · Accepted Answer · 2012-05-23 20:08:36Z

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.

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
– MJD, Commented May 23, 2012 at 21:51
Are you still working on the more general method? I would really be interested... — draks ...
– draks ..., Commented Jun 9, 2012 at 15:35

Hanson Bai · Accepted Answer · 2024-08-02 22:12:59Z

2

Here is a divisibility rule for $d$ in base $b$ , given $d$ and $b$ are relatively prime.

Let $k$ be any integer such that $k b \equiv 1 (\mod d)$ . Take the last digit of the number we're testing, multiply it by $k$ , and add it to the remaining digits, not including the last digit. Then repeat the process with the new number formed. Note that all calculations are done in base $b$ .

For example, to find if a number, say $552839$ , is divisible by 7 in base 10, we can set $k = - 2$ , since $(- 2) 10 = - 20 \equiv 1 (\mod 7)$ . Then we get the following sequence:

552839 \Rightarrow 55265 \Rightarrow 5516 \Rightarrow 539 \Rightarrow 35

Since $35$ is divisible by 7, then the original number $552839$ is also divisible by 7.

Edit - Explanation: We are essentially just repeatedly converting a number of the form $n b + m$ into $n + k m$ . Since

n b + m \equiv b (n + k m) (\mod d)

and

b

and

d

are relatively prime,

d | (n + k m)

if and only if

d | (n b + m)

, allowing the substitution.

edited Aug 2, 2024 at 22:12

answered May 2, 2021 at 21:39

Hanson Bai

895 bronze badges

1

Can you please explain how and why this method works?

Navin Murarka
– Navin Murarka

2023-09-26 04:07:40 +00:00
Commented Sep 26, 2023 at 4:07
thank you so much, this is exactly what i was looking for and you condensed it. i will edit the answer to include the proof and intuition when i have the time

god of llamas
– god of llamas

2024-06-02 00:39:34 +00:00
Commented Jun 2, 2024 at 0:39
@user471651 I added an explanation.

Hanson Bai
– Hanson Bai

2024-08-02 22:14:02 +00:00
Commented Aug 2, 2024 at 22:14

Add a comment |

Stack Exchange Network

Divisibility Rules for Bases other than $10$

3 Answers 3

You must log in to answer this question.

Linked

Hot Network Questions

Strictly Necessary Cookies

Functional Cookies

Targeting Cookies

Performance Cookies

Divisibility Rules for Bases other than 1010

3 Answers 3

You must log in to answer this question.

Linked

Related

Hot Network Questions

Divisibility Rules for Bases other than $10$