2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.