Homework Help

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

user profile pic

svjr | Student, Undergraduate | Honors

Posted September 26, 2011 at 3:19 AM via web

dislike 1 like

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

user profile pic

Matthew Fonda | eNotes Employee

Posted September 27, 2011 at 4:01 AM (Answer #1)

dislike 0 like

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