<s>[INST] 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..
 [/INST] 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& \pm 2&\pm 3&\pm4 &\pm 5 & \pm 6\\
\hline
x^2&4&-4&3&-1&-3\\
x^4&3&3&-4&1&-4\\
\hline
x^5&\pm6&\pm6&\mp3&\pm5&\pm 2
\end{matrix}$$
Thus the solution is $\;\color{red}{x\equiv6\mod 13}$.

*modulo $11$, we have
$$\begin{matrix}
x& \pm 2&\pm 3&\pm4 &\pm 5\\
\hline
x^2&4&-2&5&-1\\
\hline
x^3&\mp3&\pm5&\mp 2&\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}.$$
</s>