Find all solutions of this system: x is congruent to 2 (mod 3), 2x is congruent to 3 (mod 5) and 3x is congruent to 4 (mod 7).

### 1 Answer | Add Yours

It is possible to solve this system using the *Linear Congruence Theorem* and the *Extended Euclidean Algorithm*.

We must solve the following system of linear congruences:

`x -= 2 (mod 3)`

`2x -= 3 (mod 5)`

`3x -= 4 (mod 7)`

Conveniently, the first congruence is already written in terms of x. We can alternatively write this as *x = 3k + 2. *We will substitute of x into our next equation:

`2x -= 3 (mod 5) \implies 2(3k +2) -= 3(mod 5) \implies 6k -= -1 (mod 5)`

Then solving for k using the technique described on the Linear congruence theorem reference page, we find ` k -= 4 (mod 5)` , or *k = 5l + 4*

Plugging this back into our equation for x, we find

`x = 3k + 2 = 3(5l + 4) + 2 = 15l + 12 + 2= 15l + 14.`

We can then plug this into our last equation.

`3x -= 4 (mod 7) \implies 3(15l + 14) -= 4(mod 7) \implies 45l -= -38 (mod 7)`

Then solving for *l*, we find ` l -= 1 (mod 7)` , or ` l = 7m + 1` .

But we know x = 5l + 5, so plugging this back in we find that

`x = 5(7m + 1) + 5 = 35m + 5 + 5 = 35m + 10` .

**Therefore, the solution to the system is `x -= 10 (mod 35)` .**

### Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes