Saturday, October 31, 2015

modular arithmetic - Prove $ n equiv s(n) ($mod$ 3)$ using the fact that $ [10^n] = [1]$.





Prove $ n \equiv s(n)\ (mod\ 3)$ using the fact that $\ [10^n] = [1]$. Let $n = (a_k \times 10^k) + (a_{k-1} \times 10^{k-1}) + \cdots +(a_1 \times 10^1)+ (a_0 \times 10^0)$ and $s(n)=(a_k + a_{k-1}+ \cdots +a_1+a_0)$.



When trying to solve this question, I combined the information given and found that $$n-s(n) = (a_k \times 10^k) + (a_{k-1} \times 10^{k-1}) + \cdots +(a_1 \times 10^1)+ (a_0 \times 10^0)-(a_k + a_{k-1}+ \cdots +a_1+a_0)$$
$$=(a_k \times 10^k-a_k ) + (a_{k-1} \times 10^{k-1}-a_{k-1}) + \cdots +(a_1 \times 10^1-a_1)+ (a_0 \times 10^0-a_0)$$
$$=a_k (10^k-1) + a_{k-1} (10^{k-1}-1) + \cdots +a_1 (10^1-1)+ a_0 (1-1)$$

$$=a_k (10^k-1) + a_{k-1} (10^{k-1}-1) + \cdots +a_1 (9)$$
I'm not sure where to go from here, I thought maybe I could deduce that since, for the case of $\ [10^n] = [1]$ -- since that means that $10^n \equiv 1 (mod \ 3)$ -- I could say that since there exists an integer, call it p, such that $10^n - 1=3p$, and then put that "statement" in the parentheses in the last "=" line that I had above. I have a feeling it doesn't make sense though, and it would be incorrect.


Answer



Hint: Let $$z_n=a_n10^n+a_{n-1}10^{n-1}+...+a_1\cdot 10+a_0$$ with your hint we get
$$z_n\equiv a_n+a_{n-1}+...+a_1+a_0\mod 3$$ since $$10^i\equiv 1\mod 3$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...