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=2mk=0bk2k,biN,mN. 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|n3|2mk=0bk(1)k3|mk=0b2k+2b2k+1



ii) 5|n5|mk=0(b2k+2b2k+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}...