Saturday 30 April 2016

Find all $x\in \Bbb Z_{85}$ s.t. $(x+2)^{100}=0$.

Find all $x\in \Bbb Z_{85}$ s.t. $(x+2)^{100}=0$.



I: Taking Logarithm
Solving $(x+2)^{100}=0$ for $x\in \Bbb Z_{85}$ is equivalent to finding $x\in \Bbb Z_{85}$ s.t. $(x+2)^{100}=85y$. $$\begin{align}(x+2)^{100}&=85y\\ 100\log(x+2)&=\log(85y)\\ \log(x+2)&=\dfrac{\log(85y)}{100}\\ x+2&=10^{\log(85y)/100}\end{align}$$ The only integer values of $10^{\log(85y)/100}$ are $85,85^2,\cdots,$ (powers of $85$). [For example, when $y=85^{99}$, $10^{\log(85y)/100}=10^{\log(85)}=85$. When $y=85^{199}$, $10^{\log(85y)/100}=10^{2\log(85)}=85^2$.] It follows that $x=85-2,85^2-2,\cdots,$ (powers of $85$)$-2$. But all these values are equal to $-2\equiv_{85} 83$. Therefore, the only $x\in \Bbb Z_{85}$ satisfying the equation is $83$.

II: Solving System of Congruences
Solving $(x+2)^{100}=0$ for $x\in \Bbb Z_{85}$ is equivalent to solving $(x+2)^{100}\equiv_{85} 0$. Note that $85=5\cdot 17$. We can solve the following system of congruences: $$(x+2)^{100}\equiv_5 0\\ (x+2)^{100}\equiv_{17} 0.$$ Some calculations reveal that $$x\equiv_5 3\\ x\equiv_{17} 15.$$ Therefore, there exists $y\in \Bbb Z$ s.t. $x=3+5y$ and thus $$3+5y\equiv_{17} 15\\ 5y\equiv_{17} 12\\ y\equiv_{17} 12\cdot 7\\ y\equiv_{17} 16.$$ Finally, there exists $z\in \Bbb Z$ s.t. $x=3+5(16+17y)=83+85z\equiv_{85} 83$. Alternatively, by Chinese Remainder Theorem, the system has a unique solution $x$ modulo $85$. We have $$n_1=5,n_2=17;\;\;\;\text{and}\;\;\;n_1'=17,n_2'=5\\t_1=-2,t_2=7\\x=a_1t_1n_1'+a_2t_2n_2'=3\cdot -2\cdot 17+15\cdot 7\cdot 5=423\equiv_{85} 83.$$

No comments:

Post a Comment