system of linear congruences

Question

How can I solve this system of linear congruences? $$2x\equiv 0\, \text{mod 3}\\ 3x\equiv 2\, \text{mod 5}\\ 5x\equiv 4\, \text{mod 7}$$

I don´t know where to start, I am having a lot of troubles, can you lend me a hand please?

Answer 1

Hint $\ {-}2x\equiv -3\,$ mod $5,7\!\iff\! {\rm mod}\ 35\!:\ x\equiv 3/2\equiv 38/2\equiv 19\equiv 54.\,$ $\ 2(54)\equiv 0\pmod 3.$

Answer 2

Let's solve this equation without using the CRT. so $2x = 3k$, and this requires that $ 2 | k$. So $k = 2t$. So $x = 3t$, and $3(3t) = 5m + 2$. So $9t = 5m + 2 = 9m + 2 - 4m$, and $t = m + \dfrac{2 - 4m}{9}$. So $2 - 4m = 9p$, and $m = \dfrac{2 -9p}{4} = -2p + \dfrac{2 - p}{4}$. So $p = 2 - 4q$. So $t = -2(2 - 4q) + q + 2 - 4q = -2 + 5q$. So $x = 3(-2 + 5q) = -6 + 15q$. So $5(-6 + 15q) = 7w + 4$ gives: $-30 + 75q = 7w + 4$ or $75q = 7w + 34 = 75w + 34 - 68w = 75w + 34(1 - 2w)$. So $q = w + \dfrac{34(1 - 2w)}{75}$. So $1 - 2w = 75u$. So $w = \dfrac{1 - 75u}{2} = -38u + \dfrac{u+1}{2}$. So $u = 2z - 1$. So $w = -38(2z - 1) + z = -75z + 38$. So $q = -75z + 38 + 34(2z - 1) = -7z + 4$. So $x = -6 + 15q = -6 + 15(-7z + 4) = -105z + 54$, with $z \in \mathbb{Z}$. So the answer is: $x = -105z + 54$, with $z \in \mathbb{Z}$. Check each equation holds.

Answer 3

I would start out with the first equation: $2x\equiv 0\ \text{mod 3}$ without much difficulty you will find:

$${3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54}$$

to be solutions of the first congruence. Now you will use this set to check for prospective candidates for the second congruence: $3x\equiv 2\ \text{mod 5}$

$${9,24,39,54}$$

Seems like a very small number of candidates for the third congruence although we can continue the list if we need to ( notice the constant difference of 15 in this sequence and a constant difference of 3 in the first sequence), you can check them all easily on the last congruence .

$5x\equiv 4\ \text{mod 7}$ -- try all the candidates from the second list and exclude the ones that don't work. At last you will wind up with

$${54}$$ now , make a guess -- what is the constant difference of the elements in the last sequence? Now you can read the number theory behind it all.