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