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..

Brute-force approach: 
We want to find an $x$ such that $$x^{113} \equiv 2 \pmod{143}$$
We split $\mathbb{Z}_{143}$ into $\mathbb{Z}_{13} \times \mathbb{Z}_{11}$ since $13\cdot 11 = 143$ and $11,13$ are prime. Then, we compute the result of the congruences in $\pmod{13}$ and $\pmod{11}$, that is we solve 
$$x^{113} \equiv 2 \pmod{13}$$
$$x^{113} \equiv 2 \pmod{11}$$
On which you already correctly applied Fermat, so you can reduce the exponent always $\pmod{p-1}$ with the prime modulus. Now you solve 
$$x^{5} \equiv 2 \pmod{13}$$
$$x^{3} \equiv 2 \pmod{11}$$
By hand, to get 
$$x \equiv 6 \pmod{13}$$
$$x \equiv 7 \pmod{11}$$
CRT goes like this: You know two congruences of $x$ in two moduli, that is 
$$x \equiv a \pmod{p}$$
$$x \equiv b \pmod{q}$$
Where $p,q$ are relatively prime to each aother. From this, we can deduce the congruence of $x$ modulo $p\cdot q$ with
$$x \equiv a\cdot (q^{-1} \text{ mod }p)\cdot q + b\cdot (p^{-1} \text{ mod } q)\cdot p \pmod{pq}  $$ (Follows from https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
Through @Merlin's answer, we know that in this case
$$x \equiv 6 \pmod{13}$$
$$x \equiv 7 \pmod{11}$$
We calculate the needed inverses by using the extended eucledian algorithm (EEA):
$$13^{-1} \equiv 6 \pmod{11} $$
$$11^{-1} \equiv 6 \pmod{13} $$
We reconstruct $x$:
\begin{align} x &\equiv a\cdot (q^{-1} \text{ mod }p)\cdot q + b\cdot (p^{-1} \text{ mod } q)\cdot p \pmod{pq}\\
&\equiv 6\cdot6\cdot11 + 7\cdot6\cdot 13 \equiv 942\pmod{11\cdot13} \\
&\equiv 84 \pmod{143}
\end{align}
We check that this is indeed a solution by direct computation with wolfram alpha:

So yes, this checks out. 
