How can I find the remainder?

Question

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.

Answer 1

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

Answer 2

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