<s>[INST] Finding remainder of $123^{456}$ divided by 88 using Chinese Remainder Theorem I tried using Chinese remainder theorem but I kept getting 19 instead of 9.
Here are my steps
$$
\begin{split}
M &= 88 = 8 \times 11 \\
x_1 &= 123^{456}\equiv 2^{456} \equiv 2^{6} \equiv 64 \equiv 9 \pmod{11} \\
y_1 &= 9^{-1} \equiv 9^9 \equiv (-2)^9 \equiv -512 \equiv -6 \equiv 5 \pmod{11}\\
x_2 &= 123^{456} \equiv 123^0 \equiv 1 \pmod{8}\\
y_2 &= 1^{-1} \equiv 1 \pmod{8} \\
123^{456}
 &\equiv \sum_{i=1}^2 x_i\times\frac{M}{m_i} \times y_i
  \equiv 9\times\frac{88}{11}\times5 + 1\times\frac{88}{8} \times1 \equiv 371 
  \equiv 19 \pmod{88}
\end{split}
$$
 [/INST] By Euler's theorem, we first get $123^{40}\cong1\pmod{88}$, since $\varphi(88)=40$.  This results in $35^{16}\pmod{88}$, easily.
Now we use CRT: $\begin{cases}x\cong 35^{16}\pmod8\\x\cong35^{16}\pmod{11}\end{cases}$.
So, $x\cong3^{16}\pmod8\implies x\cong1\pmod8$, and $x\cong2^{16}\pmod{11}\implies x\cong5^4\pmod{11}\implies x\cong9\pmod{11}$, together yielding $x\cong9\pmod{88}$ by CCRT (constant case of the Chinese remainder theorem).
</s>