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}
$$
 A: You used the inverse of $x_i$ instead of the inverse of $\frac{M}{m_i}$. So for example,
$$
9 \cdot \frac{88}{11} \cdot 5 + 1 \cdot \frac{88}{8} \cdot 1 \equiv 0 + 1 \cdot 11 \cdot 1 \equiv 3 \not \equiv 1\pmod{8}.
$$
If you use the inverse of $\frac{M}{m_i}$ instead, you would have
$$
x_1 \cdot \frac{88}{11} \cdot 8^{-1} + x_2 \cdot \frac{88}{8} \cdot 11^{-1} \equiv 0 + 1 \cdot 11 \cdot 11^{-1} \equiv 1\pmod{8}.
$$
A: $y_1$ should've been the inverse of $8\pmod{11}$, not of $9\pmod{11}$, so $y_1=7$.
Similarly, $y_2$ should've been the inverse of $11\pmod 8$, not of $1\pmod 8$, so $y_2=3$.
Therefore, the result is: $9\times\frac{88}{11}\times \color{red}{7}+1\times\frac{88}{8}\times \color{red}{3}=537\equiv 9\pmod{88}$
A: You used an incorrect CRT formula. It should be: for coprime $\,m,n,\,$ and $\,c^{-1}_{\ n}:= c^{-1}\bmod n$
$\qquad\begin{align} &x\equiv a\!\!\pmod{\!m}\\ &x\equiv b\!\!\pmod{\!n}\end{align}\iff x\,\equiv\, a\,n(n^{-1}_{\ m}) + b\,m(m^{-1}_{\ n})\ \ \pmod{\!mn}$
To help remember the formula note that it is easy to see it is correct since
$\qquad\qquad\qquad\quad\ \ \bmod \color{#c00} m\!:\ \  x\,\equiv\, a\, \underbrace{n (n^{-1})}_{\large \equiv\ 1\ }\, +\, \underbrace{b\, \color{#c00}m\, (\cdots)}_{\large \color{#c00}{\equiv\ 0}}\, \equiv\, a$
i.e. $\bmod (m,n)\!:\,\ n\, n^{-1}_{\ m}\equiv (1,0),\,\ m\,m^{-1}_{\ n}\equiv (0,1)\,$ so the formula is simply
$$ x\equiv (a,b) \equiv  a (1,0) + b (0,1)\qquad\qquad$$
See this answer for further discussion of this viewpoint (including an example with $3$ moduli).
A: Your calculations look correct except for the last line which I don't understand.
One you get $x_1$ and $x_2$, you could simply write
$x=123^{456}=9+11k$ (from $x_1$)
so reducing mod $8$ yields
$x \equiv 1+3k \pmod{8} \equiv 1 \pmod{8}$ (from $x_2$)
therefore
$3k\equiv0 \pmod{8}$ and since $\gcd(3,8)=1$, $3$ is invertible mod $8$, so $k \equiv 0 \pmod{8}$
hence $x=9+11(0+8k')=9+88k' \equiv 9 \pmod{88}$
A: Modulo $88$ one has $$123^{456} = 35^{456} = (35^2)^{228} = (-7)^{228} = ((-7)^6)^{38} = (-7)^{38} = ((-7)^6)^6 \times 49 = (-7)^6 \times 49 = -7 \times 49 = -343 = 9 \quad [88]$$
A: $123^{456}\equiv 2^6=64\equiv9\bmod 11$.
$123^{456}\equiv 3^0=1\equiv9\bmod 8$.
Therefore, by the constant case of the Chinese Remainder Theorem, $123^{456}\equiv9\bmod88$.
A: 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).
