How can I find the remainder? How can I find the remainder when 
$$(12371^{56}+34)^{28}$$
is divided by $111$.
I have tried congruences modulo $111$ but without any success.

$111=3\cdot 37$. You can use Euler's criterion (EC) with Quadratic reciprocity.
$$\left(\frac{13}{37}\right)=\left(\frac{37}{13}\right)=\left(\frac{-2}{13}\right)=-1$$
$$12371^{56}\equiv 13^{56}\equiv 13^2\left(13^{(37-1)/2}\right)^3\stackrel{\text{EC}}\equiv 21\left(-1\right)^3\equiv 16\pmod{\! 37}$$
$$\left(12371^{56}+34\right)^{28}\equiv 13^{28}\stackrel{\text{EC}}\equiv -13^{10}\equiv -\left(13^5\right)^2\equiv -4\pmod{\! 37}$$
because $13^5\equiv 21^2\cdot 13\equiv -3\cdot 13\equiv -2\pmod{\! 37}$.
$$\left(12371^{56}+34\right)^{28}\equiv \left((-1)^{56}+1\right)^{28}\equiv (-1)^{28}\equiv 1\pmod{\! 3}$$
$x\equiv -4\equiv 70\pmod{\! 37},\, x\equiv 1\equiv 70\pmod{\! 3}$ and
$$3,37\mid x-70\iff 111\mid x-70$$
