31
$\begingroup$

Aside from the zero rule (a number ending with zero means it is divisible by the base number and its factors), why is it that other rules cannot apply in different bases?

In particular for 3 one can just sum all digits and see if it is divisible. What relation exists between 10 and 3 to have this property? Does this property exist in another base?

Also: Are there divisibility rules for base 2? Are there general divisibility formulae for all bases?

$\endgroup$
  • 2
    $\begingroup$ See math.stackexchange.com/questions/328562/… $\endgroup$ – lab bhattacharjee Oct 3 '16 at 6:45
  • 4
    $\begingroup$ Because 10=3^2+1. If 10 = n+1 then the division rule work for n. So in base eight division rule works for 7. $21_{10}=25_8$ AND 2+5= 7 so divisible by 7. $24_{10}=17_{17} $ and 1+7=8 so divisible by 4= root (16) $\endgroup$ – fleablood Oct 3 '16 at 6:57
  • 1
    $\begingroup$ In base two. If ends with 0 is divisible by 2. $\endgroup$ – fleablood Oct 3 '16 at 7:08
  • 1
    $\begingroup$ In base 2. If the even digits add up to a multiple of 3 more or less than the sum of the odd digits than the number is divisible by 3. $\endgroup$ – fleablood Oct 3 '16 at 7:10
  • 1
    $\begingroup$ These tricks are used with base 256, 65536 etc when calculating checksums to avoid certain expensive operations. Handy stuff. $\endgroup$ – pipe Oct 3 '16 at 16:16
34
$\begingroup$

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

$\endgroup$
16
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

The 3 divisible rule works because of the fact that 9,99,999... are all divisible by 3.

For example, 471 is divisible by 3 because 4+7+1 =12 divisible.

Think of this: Any number divisible by 3 is still divisible if you subtract any multiple of 3 by the number itself.

471 = 4*100+7*10+1

Try subtracting it by 99*4+9*7 you will be left with 4*(100-99)+7*(10-9)+1, which is just the sum of the digits. You can thus see why the rule above works.

$\endgroup$
  • 2
    $\begingroup$ True.... but why won't it work in other bases? Which was the question. $\endgroup$ – fleablood Oct 3 '16 at 6:58
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Lots of answers touch on the exact reason these rules don't (or occasionally, do) work in other bases. Let me try it from a slightly different tack though, which I think might be more generally helpful.

Basically: there is no reason they ought to hold in other bases. The reason is that you're talking about a connection between two different things.

The first is the properties of an actual number. Consider 10 - the number of fingers you (probably) have. I denoted it with the digits 10, but I could have written ten, or 12 (in base 8) or A (in base 16) or whatever; the number isn't changing only our word for it. The property "x is divisible by three" doesn't depend on what base we're expressing x in; it's either true or false for the actual number we put in for x.

On the other hand, the property "the least significant digit of x is zero" absolutely depends on the base we express x in. If x is the number of fingers I have, then we still don't know if the property above is true - it depends on the base. In base 10, it's true; in base 8, it's false. And so on.

Here's the point, then. Divisibility is invariant of base; that is, it doesn't matter how you represent the number, it's either divisible by three (or five or nine or whatever) or it isn't. On the other hand, digits are not invariant of base; if you change the base, whatever your digit properties are will change, too.

So you shouldn't expect the divisibility rules to hold. Now occasionally they do, but that's the surprising case, not the norm.

A huge part of math is training your intuition - not just knowing what is and isn't true, but having enough sense of what's going on to know when to be surprised! And curiosity is the way you learn it - by asking this question, you're well on your way!

$\endgroup$
1
$\begingroup$

Numbers are conceptually independent of their digits (as shown by the difference in bases but congruence if applied to counting sticks). The purpose of divisibility tricks is meant only to apply to the numbers of base 10, effectively ignoring the true value of the number and focusing plainly on the external digits itself. Sort of like when dividing by 3, 12 fits perfectly base 10, but in base 3 [5] does not.

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