Solve the system of linear congruences below by finding all $x$ that satisfy it.

Question

Question: Solve the system of linear congruences below by finding all $x$ that satisfy it. Hint — try rewriting each congruence in the form $x \equiv a \pmod b$.

$2x \equiv 1 \pmod3$

$3x \equiv 2 \pmod5$

$5x \equiv 4 \pmod7$

So I tried following that hint, and I have:

$x \equiv 2 \pmod3$

$x \equiv 4 \pmod5$

$x \equiv 5 \pmod7$

Firstly, is this correct? Second, where do I go from here? I calculated that $M = 3 \times 5 \times 7 = 105$ and the individual $M_i$'s, but now I'm stuck in a circle, because reducing from there gives me back the original equations. Any tips?

Answer 1

What you did is correct. Now, apply the chinese remainder theorem.

Answer 2

from the first both equations we get $$\frac{3}{2}(1+3m)=2+5n$$ or $$9m-10n=1$$ solving this Diophantine equation we get $$m=9+10C$$ $$n=8+9C$$ with this two equations you can calculate $x$

Answer 3

Using the Extended Euclidean Algorithm, one implementation can be found in this answer, we can solve the three equations $$ 3x+35y=1=12\cdot3-1\cdot35 $$ $$ 5x+21y=1=-4\cdot5+1\cdot21 $$ $$ 7x+15y=1=-2\cdot7+1\cdot15 $$ which gives the equations $$ \begin{align} -35&\equiv1\pmod3\\ -35&\equiv0\pmod5\\ -35&\equiv0\pmod7 \end{align}\tag1 $$ and $$ \begin{align} 21&\equiv0\pmod3\\ 21&\equiv1\pmod5\\ 21&\equiv0\pmod7 \end{align}\tag2 $$ and $$ \begin{align} 15&\equiv0\pmod3\\ 15&\equiv0\pmod5\\ 15&\equiv1\pmod7 \end{align}\tag3 $$ Adding $2$ times $(1)$ to $4$ times $(2)$ and $5$ times $(3)$ should give an answer mod $105$.