how to solve $x^{113}\equiv 2 \pmod{143}$ I need to solve $x^{113} \equiv 2 \pmod{143}$ 
$$143 = 13 \times 11$$

I know that it equals to $x^{113}\equiv 2 \pmod{13}$ and $x^{113}\equiv 2 \pmod{11}$

By Fermat I got

1)  $x^{5} \equiv 2 \pmod{13}$

2)  $x^{3} \equiv 2 \pmod{11}$

Now I'm stuck..
By the Chinese remainder theorem, you have to solve first
$$\begin{cases}x^{113}\equiv2\mod13\\x^{113}\equiv2\mod11\end{cases}$$
Now Little Fermat says for any $x\not\equiv 0\mod 13\enspace(\text{resp. }11)$, one has $x^{12}\equiv 1\mod 13$, resp. $x^{10}\equiv 1\mod 11$. Hence the system of congruences is equivalent to
$$\begin{cases}x^{113\bmod 12}\equiv x^5\equiv2\mod13,\\x^{113\bmod 10}\equiv x^3\equiv2\mod11.
\end{cases}$$

Let's examine the different possibilities for $x$.

We can eliminate the values $0$ and $1$. Hence,


modulo $13$, let's draw a table, using the fast exponentiation algorithm:
$$\begin{matrix}
x&amp; \pm 2&amp;\pm 3&amp;\pm4 &amp;\pm 5 &amp; \pm 6\\
\hline
x^2&amp;4&amp;-4&amp;3&amp;-1&amp;-3\\
x^4&amp;3&amp;3&amp;-4&amp;1&amp;-4\\
\hline
x^5&amp;\pm6&amp;\pm6&amp;\mp3&amp;\pm5&amp;\pm 2
\end{matrix}$$
Thus the solution is $\;\color{red}{x\equiv6\mod 13}$.
modulo $11$, we have
$$\begin{matrix}
x&amp; \pm 2&amp;\pm 3&amp;\pm4 &amp;\pm 5\\
\hline
x^2&amp;4&amp;-2&amp;5&amp;-1\\
\hline
x^3&amp;\mp3&amp;\pm5&amp;\mp 2&amp;\mp5
\end{matrix}$$
Here the solution is $\;\color{red}{x\equiv-4\mod 11}$.


To solve this system of simultaneous congruences, we need a Bézout's relation between $13$ and $11$:
$$6\cdot 11-5\cdot13=1.$$
The solutions of the system of congruences is
$$x\equiv\color{red}{6}\cdot 6\cdot 11-(\color{red}{-4})\cdot5\cdot 13\equiv656\equiv \color{red}{84 \mod 143}.$$
The first congruence tells you $x \equiv 6 \pmod {13}$ and the second tells you $x \equiv 7 \pmod {11}$, now apply the Chinese remainder theorem to get your answer.