Congruence system

Question

Could you please help me to find out the solution of the system

$$ \begin{array}{ccc} x&\equiv&2& (\textrm{mod} \ 5) \\ x&\equiv&3& (\textrm{mod} \ 4) \\ x&\equiv&9& (\textrm{mod} \ 6) \end{array} $$

Using the Chinese reminder theorem. Here is my progress: the numbers $b_1=2$, $b_2=3$ and $b_3=3$ are particular solutions of each congruence, respectively. We compute $$ y_1= 6\cdot4=24, y_2= 5\cdot6=30, y_1= 5\cdot4=20 $$

The theorems guarantees that the following congruences have solution

$$ 24x_1\equiv1 \ (\textrm{mod} \ 5), 30x_2\equiv1 \ (\textrm{mod} \ 4), 20x_3\equiv1 \ (\textrm{mod} \ 6), $$ ie. $$ 4x_1\equiv1 \ (\textrm{mod} \ 5), 2x_2\equiv1 \ (\textrm{mod} \ 4), 2x_3\equiv1 \ (\textrm{mod} \ 6), $$

I can get $x_1=4$, but what about $x_2$ and $x_3$?

The answer, according to Wolfram Alpha is $x\equiv27 \ (\textrm{mod} \ 60)$

Answer 1

The congruence $2x_2\equiv1\pmod4$ has no solutions as an odd number cannot be a multiple of $2$.

One needs to decompose the system so that the moduli (in our case $5, 4$, and $6$) are mutually prime, which is the hypothesis of Chinese Remainder Theorem.

Now observe that the congruence $x\equiv9\equiv3\pmod6$ is equivalent with $$x\begin{cases}\equiv0\pmod3\\\equiv1\pmod2\end{cases},$$ by Chinese Remainder Theorem. Moreover, the congruence $x\equiv1\pmod2$ is implied by another congruence $x\equiv3\pmod4$. So we can reduce the original system to $$ x\begin{cases}\equiv2\pmod5\\\equiv3\pmod4\\\equiv0\pmod3\end{cases}. $$

I suppose you can continue from here.

---

Hope this helps.

Answer 2

You have $$ \begin{array}{ccc} x&\equiv&2& (\textrm{mod} \ 5) \\ x&\equiv&3& (\textrm{mod} \ 4) \\ x&\equiv&9& (\textrm{mod} \ 6) \end{array} $$ $x=5k+2$

So $5k+2 \equiv 3 (mod 4)$

$5k \equiv 5 (mod 4)$

So $k \equiv 1 (mod 4)$

Or $k=4m+1$

$\therefore x=5(4m+1)+2$

Or $x=20m+7$

Now, $20m+7 \equiv 9 (mod 6)$

$\Rightarrow 20m \equiv 2 (mod 6)$

$20m \equiv 20 (mod 6)$ (adding 18)

So $m \equiv 1 (mod 3)$

Or $m=3p+1$

$x=20(3p+1)+7$

$x=60p+27$

$\therefore x \equiv 27 (mod 60)$

Hope this helps :)