Example 8 Find the remainder when $\left(12371^{55}+34\right)^{28}$ is divided by 111.
From $12371=111^{2}+50$, we get $12371 \equiv 50(\bmod 111)$. By Lemma 3, we have
$$12371^{56} \equiv 50^{56}(\bmod 111)$$

We also have $(50)^{28}=(125000)^{9}(50), 125000 \equiv 14(\bmod 111)$, so by Lemma 3, we get
$$(50)^{28} \equiv(14)^{9}(50)(\bmod 111)$$

Furthermore, $14^{3} \equiv 80(\bmod 111),(80)^{3} \equiv 68(\bmod 111) ，(68)(50) \equiv$ $70(\bmod 111)$, which gives us
$$(50)^{28} \equiv 70(\bmod 111)$$

By Lemma 3, we have $(50)^{*} \equiv 70^{2}(\bmod 111)$. We also have $70^{2} \equiv 16$ $(\bmod 111)$, so by (20) we get $12371^{56} \equiv 16(\bmod 111)$. By Lemma 3, we have $\left(12371^{56}+34\right)^{28} \equiv 50^{28}(\bmod 111)$. By (22), we get $\left(12371^{56}+34\right)^{28} \equiv 70(\bmod 111)$. Therefore, the remainder when $\left(12371^{56}+34\right)^{28}$ is divided by 111 is 70.