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,bi∈N,m∈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⇔3|∑2mk=0bk(−1)k⇔3|∑mk=0b2k+2b2k+1
ii) 5|n⇔5|∑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