1
$\begingroup$

So, during the study of congruences and divisibility I encountered the usual divisibility rules for the decimal system. However, as an exercise I received the following claims that I have to prove in the binary system, i.e. now a natural number $n$ is represented as $n = \sum_{k=0}^{2m} b_k2^k, b_i \in \mathbb{N}, m \in \mathbb{N}$. With those I struggle quite a bit as it seems that I don't yet have fully grasped the concept of modular arithmetic.

The exercise is to show that

i) $3 | n \Leftrightarrow 3|\sum_{k=0}^{2m} b_k(-1)^k \Leftrightarrow 3|\sum_{k=0}^{m} b_{2k} + 2b_{2k+1}$

ii) $5|n \Leftrightarrow 5|\sum_{k=0}^{m} (b_{2k} + 2b_{2k+1})(-1)^k$

Moreover, I have to find a rule for the divisivility by 7. Since I do not know how to go about proving the above, I am even more lost finding a rule.

$\endgroup$
1
$\begingroup$

Hint. Note that $2\equiv -1\pmod{3}$ and $4\equiv -1\pmod{5}$. Hence $$n = \sum_{k=0}^{2m} b_k2^k\equiv \sum_{k=0}^{2m} b_k(-1)^k \pmod{3}$$ and $$n = \sum_{k=0}^{2m+1} b_k2^k=\sum_{k=0}^{m} b_{2k}2^{2k}+\sum_{k=0}^{m} b_{2k+1}2^{2k+1}\equiv \sum_{k=0}^{m} b_{2k}(-1)^{k} +\sum_{k=0}^{m} b_{2k+1}2\cdot(-1)^{k} \pmod{5}.$$ Can you take it from here?

$\endgroup$
  • $\begingroup$ Well, first of all thanks for your fast reply. Second, may I ask you some questions for clarification? Why do we need to sum over $2m$ instead of $m$ to begin with? So, okay, $n \equiv \sum_{k=0}^{2m} b_k(-1)^k (\mod 3)$ -- but what to conclude from that? For me that just means that both leave the same residue after division. But where is the equivalence here? $\endgroup$ – Taufi Nov 28 '16 at 15:54
  • $\begingroup$ @Taufi The final index $2m$ is not so important. If $n$ has less than $2m+1$ digits then the extra digits are zero. Moreover, $n$ is divisible by $d$ iff the residue modulo $d$ is zero, So if $n$ and $m$ have the same residue modulo $d$ and one of them is divisible by $d$ then also the other is divisible by $d$ and viceversa (equivalence). $\endgroup$ – Robert Z Nov 28 '16 at 16:27
1
$\begingroup$

Notice that both sums break the number up into pairs of binary digits: you’re adding (or alternately adding and subtracting) the quantities $b_{2k}+2b_{2k+1}$. Look at a concrete example, say $1101001011$.

$$\begin{array}{rcc} k:&4&3&2&1&0\\ b_{2k+1}b_{2k}:&11&01&00&10&11\\ b_{2k}+2b_{2k+1}:&3&1&0&2&3 \end{array}$$

The proposed test for divisibility by $3$ then adds the numbers in the bottom row to get $9$, which is divisible by $3$, and indeed $1101001011_{\text{two}}=843=3\cdot281$ is divisible by $3$.

In fact the bottom row is just the base four representation of $n$:

$$\sum_{k=0}^{2m}b_k2^k=\sum_{k=0}^m(b_{2k}+2b_{2k+1})2^{2k}=\sum_{k=0}^m(b_{2k}+2b_{2k+1})4^k\;,$$

and each $b_{2k}+2b_{2k+1}$ is $0,1,2$, or $3$. If you think of it in terms of the base four representation, this test is just like the usual test for divisibility by $9$ of a number written in ordinary decimal notation, and it works for the same reason: $3$ is $1$ less than the base, just as $9$ is $1$ less than our usual base of $4$.

The general result is that if you write a positive integer in base $b$, that integer is divisible by $b-1$ if and only if the sum of its digits is divisible by $b-1$ and, more generally, the integer and the sum of its digits are congruent modulo $b-1$.

To see this, let $n=\sum_{k=0}^md_kb^k$, where each $d_k\in\{0,1,\ldots,b-1\}$. Clearly $b\equiv 1\pmod{b-1}$, so $b^k\equiv 1^k\pmod{b-1}$, and of course $1^k=1$, so

$$n=\sum_{k=0}^md_kb^k\equiv\sum_{k=0}^md_k\pmod{b-1}\;.$$

The test for divisibility by $5$ is similar, except that it takes the alternating sum of the base four digits. If you know the test for divisibility by $11$ in our ordinary decimal system, you’ll recognize this as analogous, and again it works more generally: an integer written in base $b$ is congruent mod $b+1$ to the alternating sum of its digits, and in particular it’s divisible by $b+1$ if and only if the alternating sum of its digits is. Again the calculation is straightforward: we use the fact that $b\equiv-1\pmod{b+1}$, so that

$$\sum_{k=0}^md_kb^k\equiv\sum_{k=0}^md_k(-1)^k\pmod{b+1}\;.$$

In the present case $b$ is really $4$, even though we’re actually working with numbers written in binary: as noted above, using the terms $b_{2k}+2b_{2k+1}$ is in effect just converting the number to base four.

For the final part of the question you’ll want a base different from $4$, but it will still be one such that the representation in that base is very, very easily derivable from the binary representation.

$\endgroup$
1
$\begingroup$

Let $$n=\sum_{k\geq0} b_k2^k$$ with $b_k\in\{0,1\}$. From $$2^k=(-1)^k\quad({\rm mod}\ 3),\qquad2^{2j}=(-1)^j\quad({\rm mod}\ 5),\qquad 2^{3j}=1\quad({\rm mod}\ 7)$$ it follows that $$\eqalign{n&=\sum_{k\geq0}(-1)^kb_k\qquad({\rm mod}\ 3)\ ,\cr n&=\sum_{j\geq0}(b_{2j}+2b_{2j+1})(-1)^j\qquad({\rm mod}\ 5)\ ,\cr n&=\sum_{j\geq0}(b_{3j}+2b_{3j+1}+4b_{3j+2})\qquad({\rm mod}\ 7)\ .\cr}$$

$\endgroup$
0
$\begingroup$

Although the question about 3 and 5 refers to binary numbers, it's really about numbers in base 4. Each digit in base 4 is made of 2 binary digits. E.g. 19 is 10011 in binary. To get it in base 4, add a 0 at the front to make an even number of binary digits, then group the binary digits in pairs 01,00,11, which gives 103 in base 4. I think the person who set the question has slipped up: the top index $2m$ should be $2m - 1$, to make an even number of binary digits, and the top index $m$ should be $m-1$. The formulae in the question follow because the rules for divisibility by 3 and 5 in base 4 are analogous to the rules for divisibility by 9 and 11 in base 10. For divisibility by 7, I suppose you're expected to divide the binary digits into groups of three and work in base 8.

$\endgroup$
0
$\begingroup$

Hint $ $ It's immediate decomposing $\,b(x) = \sum _k b_k x^k \,$ into even and odd parts

$$\begin{align} b(x) &= b_0(x^2)+ x\, b_1(x^2)\\ \\ \Rightarrow\ \ {\rm mod}\ 3\!:\ b(2) &\equiv\ b_0(\color{#c00}1)\,+\,2\,b_1(\color{#c00}1)\quad\ \ \ {\rm by}\ \ \color{#c00}{2^2\,\equiv\, 1} \\ \\ \Rightarrow\ \ {\rm mod}\ 5\!:\ b(2)&\equiv b_0(\color{#0a0}{-1})+2\,b_1(\color{#0a0}{-1})\ \ {\rm by}\ \ \ \color{#0a0}{2^2\equiv -1} \end{align}$$


Remark $\ $ Analogous results hold mod $\,d^2\pm1\,$ in radix $d\ $ by using $\,\color{#c00}{d^2\equiv \mp 1},\,$ e.g. the familiar casting out $\,99\,$ or $101$ in decimal notation. Using modular arithmetic makes it easy to do even much hairier modular magic such as casting out ninety-one's using $\ 91 = 10^2\!-10+1,\,$ e.g.

$${\rm mod}\ 91\!:\,\ 6543210\, \equiv\, 0\! -\!2\! \!-3\! +\!5\!+\!6 + (1\! +\!2\! -\!4\! -\!5) 10\, \equiv\, 6\!-\!60\, \equiv\, {37}$$

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