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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.