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.
 A: $$\begin{align}12371&\bmod111=50\\
12371^2&\bmod111=50^2&\bmod111=58\\
12371^4&\bmod111=58^2&\bmod111=34\\
12371^7&\bmod111=(50\cdot58\cdot34)&\bmod111=32\\
12371^{14}&\bmod111=32^2&\bmod111=25\\
12371^{28}&\bmod111=25^2&\bmod111=70\\
12371^{56}&\bmod111=70^2&\bmod111=16.
\end{align}$$
Then
$$(12371^{56}+34)^{28}=50^{28}\bmod111=70.$$
A: $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$$
