Solve the set of simultaneous congruences using Chinese Remainder Theorem
$\begin{cases}
2x \equiv 1 \pmod{5} \\
3x \equiv 9 \pmod{6} \\
4x \equiv 1 \pmod{7} \\
5x \equiv 9 \pmod{11} \\
\end{cases}$
This is what I got so far:
I simplify:
$2x \equiv 1 \pmod 5$ becomes $x \equiv 3 \pmod 5$
$3x \equiv 9 \pmod 6$ has $3$ solutions since $\gcd(3,6)=3$ they are $x = 17$, $19$, or $21 \pmod 6$.
$4x \equiv 1 \pmod 7$ becomes $x \equiv 2 \pmod 7$
$5x \equiv 9 \pmod {11}$ becomes $x \equiv 4 \pmod {11}$
By CRT, and substituting the $3$ different solutions, I got:
$x \equiv 653 \pmod{2310}$, $x \equiv 1423 \pmod{2310}$ and $x \equiv 2193 \pmod {2310}$.
But, the key answer from the book is $x \equiv 653 \pmod{770}$.
I am struggling to figure out how to get $x = 653 \pmod{770}$. I need help. Thank you.
Best Answer
$\begin{cases} 2x \equiv 1 \pmod{5} & \times 3 \quad 6\equiv 1\pmod 5 & x\equiv \color{green}3 \pmod 5\\ 3x \equiv 9 \pmod{6} & /3 \text{ whole equation} & x\equiv 3\equiv \color{green}1\pmod 2\\ 4x \equiv 1 \pmod{7} & \times 2 \quad 8\equiv 1\pmod 7 & x\equiv \color{green}2\pmod 7\\ 5x \equiv 9 \pmod{11} & \times 9 \quad 45\equiv 1\pmod {11} & x\equiv 81\equiv \color{green}4\pmod{11}\\ \end{cases}$
By Chinese remainder theorem :
$\begin{cases} N=2.5.7.11=770\\ N_5=2.7.11=\color{red}{154} &\quad\equiv 4\equiv \color{blue}4^{-1}\pmod 5\\ N_2=5.7.11=\color{red}{385} &\quad\equiv 1\equiv \color{blue}1^{-1}\pmod 2\\ N_7=2.5.11=\color{red}{110} &\quad\equiv 5\equiv \color{blue}3^{-1}\pmod 7\\ N_{11}=2.5.7=\color{red}{70} &\quad\equiv 4\equiv \color{blue}3^{-1}\pmod {11}\\ \end{cases}$
$x\equiv (\color{red}{154}\times \color{blue}4\times \color{green}3)+(\color{red}{385}\times \color{blue}1\times \color{green}1)+(\color{red}{110}\times \color{blue}3\times \color{green}2)+ (\color{red}{70}\times \color{blue}3\times \color{green}4)\equiv 3733\pmod{770}$
Let's have $m=\gcd(a,b,c)$ and $ax\equiv b\pmod c$
$\begin{cases} a=m\alpha\\ b=m\beta\\ c=m\gamma\\ \end{cases}$
$\exists k\mid ax=b+kc\iff m\alpha x=m\beta+km\gamma\iff \alpha x=\beta+k\gamma$
Which is $\alpha x\equiv \beta \pmod{\gamma}$, so you can divide the whole equation by $m$.
This is the step you missed you to conclude easily.