$2^x\equiv 2017\pmod{3^{11}}$ and $2^x\equiv 2016\pmod{11^3}$

Question

Find an integer $x$ such that $2^x\equiv 2017\pmod{3^{11}}$ and $2^x\equiv 2016\pmod{11^3}$

How can I solve this question?

Answer 1

First find $y$ such that $2^y\equiv 2017\pmod{3^{11}}$ and $z$ such that $2^z\equiv 2016 \pmod{11^3}$. (These are discrete logarithm problems, which are hard in general, but if you have computer support, a brute-force search is feasible with moduli as small as these).

Then you need to find $x$ such that $$x\equiv y\pmod{\varphi(3^{11})} \qquad\text{and}\qquad x\equiv z\pmod{\varphi(11^3)}.$$ This is almost just an application of the Chinese Remainder Theorem, except that $\varphi(3^{11})$ and $\varphi(11^3)$ have a factor of $2$ in common -- so better hope that $x$ and $y$ are either both odd or both even, and you can then use the CRT with the three moduli $2$, $3^{10}$, and $5\cdot 11^2$.