Saturday 12 August 2017

self learning - Divisibility rules in the binary system



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.


Answer



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?


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...