Processing math: 100%

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