Use the Chinese remainder theorem to find the general solution of $x \equiv a \pmod {2^3}, \; x \equiv b \pmod {3^2}, \; x \equiv c \pmod {11}$ Help! Midterm exam is coming, but i still unable to solve this simple problem using the Chinese remainder theorem.
$$x \equiv a \pmod {2^3}, \quad x \equiv b \pmod {3^2}, \quad x \equiv c \pmod {11}.$$
 A: From the condition of the equation we have:
$$x \equiv a \pmod 8 \implies x = 8k + a$$
$$x \equiv b \pmod 9 \implies x = 9n + b$$
$$x \equiv c \pmod {11} \implies x = 11m + c$$
Now we have:
$$8k+a=9n+b$$
$$8k+a\equiv b \pmod 9$$
$$8k\equiv b-a \pmod 9$$
Having actual values would be easier to get congruence relation for k modulo 9, but now we'll use:
$$k \equiv \frac{b-a + 9s}{8} \pmod 9 \implies k = 9t + \frac{b-a+9s}{8}$$
Note that if we add 9s on the RHS the congruence relation won't change. Sowe add $9s$ in order to get an integer when we divide by 9.
Now substitute back we have:
$$x=8k+a = 8\left(9t + \frac{b-a}{8}\right) = 72t + b-a + 9s$$
Now using this relation for x we do the same thing for this realtion and $x = 11m + c$. It maybe clearer to you with example:

$$x \equiv 3 \pmod 8 \implies x = 8k + 3$$
$$x \equiv 2 \pmod 9 \implies x = 9n + 2$$
$$x \equiv 5 \pmod {11} \implies x = 11m + 5$$
$$8k + 3 = 9n + 2$$
$$8k + 3 \equiv 2 \pmod 9$$
$$8k \equiv -1 \equiv 8 \pmod 9$$
$$k \equiv 1 \pmod 9 \implies k = 9t + 1$$
Now we substitute back:
$$x = 8k + 3 = 8(9t+1) + 3 = 72t + 8 + 3 = 72t + 11$$
Now we repeat the same procedure:
$$72t + 11 = 11m + 5$$
$$72t + 11 \equiv 5 \pmod {11}$$
$$72t \equiv 5  \equiv 720 \pmod {11}$$
$$t \equiv 10 \pmod {11} \implies t = 11s + 10$$
Now we substitue:
$$x = 72t + 11 = 72(11s + 10) + 11 = 792s + 720 + 11 = 792s + 731$$
We have a congruence relation for $x$:
$$x \equiv 731 \pmod{792}$$
You can see that $792=8\cdot 9 \cdot 11$, that's because all moduli are coprime, otherwise we would end up with the least common multiple of the moduli.
A: We know that $x$ has the form:
$$
x=a\cdot(s\cdot 3^2\cdot 11)+b\cdot(t\cdot 2^3\cdot 11)+c\cdot(r\cdot 2^3\cdot 3^2)
$$
where $s,t$ and $r$ have been found so that
$$
\begin{align}
s\cdot 3^2\cdot 11&\equiv 1\mbox{ mod }2^3\\
t\cdot 2^3\cdot 11&\equiv 1\mbox{ mod }3^2\\
r\cdot 2^3\cdot 3^2&\equiv 1\mbox{ mod }11
\end{align}
$$
Just try $s=1$, $s=2$ etc. until you find $s$ and similarly for $t$ and $r$. Or use Bezout's identity from the extended Eucledian algorithm to find $s,t$ and $r$.
A: The general method to find such a number, is to solve for $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$, where the numbers in brackets represent a number modulo $8$, $9$, $11$.  Since the number $(1,1,1) = 1$, it is necessary to solve only for two of them.
For $(1,0,0)$, we start off with $99 = (3, 0, 0)$.  Since the first multiple of $3$ to exceed eight by 1, is 9, we then have  $3\times 99 = (1,0,0)$.
For $(0,1,0)$, we start with $8\times 11 = (0,7,0)$.  It then is a matter of multiplying this by $4$ to get $352 = (0,1,0)$
We could do the same for the next, but note that $(1,1,1)=1+792$, and thence $(0,0,1) = (1,1,1)-(1,0,0)-(0,1,0)$, gives $793 - 297 - 352 = 144$  This is indeed $(0,0,1)$.
So we find here that $a=297$, $b=352$ and $c=144$, the sum is $1 \pmod{8\cdot 9 \cdot 11}$.
