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

mfonda's profile pic

Posted on

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)` .

 

We’ve answered 327,520 questions. We can answer yours, too.

Ask a question