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..
 A: 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}.$$
A: 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. 
A: $x^5 \equiv 2 (\mod13)$
$x^{12} \equiv 1(\mod 13)$ (Femat's little theorem.)
$5\cdot5\equiv 1 (\mod 12)\\
(2^5)^5 \equiv 2 (\mod 13)\\
(2^5) \equiv 6 (\mod 13)\\
x\equiv 6 (\mod 13)$
Now use the same logic mod 11
$x^{10} \equiv 1(\mod 11)\\
3\cdot7 \equiv 1(\mod 10)\\
(2^7)^3 \equiv 2(\mod 11)\\
(2^7) \equiv 7(\mod 11)\\
7^3 \equiv 2(\mod 11)\\
x\equiv 7(\mod 11)$
Can you get home from here?
A: 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.
