Homework Help

Solve: x is congruent to 5 (mod 6), 10x is congruent to 11 (mod 13), x is congruent to...

user profile pic

svjr | Student, Undergraduate | Honors

Posted October 6, 2011 at 4:05 AM via web

dislike 0 like

Solve: x is congruent to 5 (mod 6), 10x is congruent to 11 (mod 13), x is congruent to 4 (mod 5)

 

Tagged with math, number theory

1 Answer | Add Yours

user profile pic

justaguide | College Teacher | (Level 2) Distinguished Educator

Posted October 6, 2011 at 11:35 PM (Answer #1)

dislike 0 like

We have to solve:

x`-=` ` ` 5(mod 6) ...(1)

10x`-= ` 11(mod 13) ...(2)

x`-= ` 4(mod 5) ...(3)

From (1), we get x = 6k + 5

substitute in (2)

10(6k + 5) `-=` ` ` 11(mod 13)

=> 60k + 50`-=` 11(mod 13)

=> 60k `-=` -39(mod 13)

gcd(60/13) = 1, there is only 1 solution for k in the set {0,1,2...12} which is k `-=` 0(mod 13)

k = 13m => x = 6(13m) + 5 = 78m+ 5

Substituting in (3)

78m + 5`-=` 4(mod 5)

=> 78m`-=` -1(mod 5)

gcd(78, 5) = 1. m has one solution in {0, 1, 2, 3, 4} which is m`-=` 3(mod 5)

m = 5n + 3

x = 78(5n + 3) + 5 = 390n + 239

x`-=` 239(mod 390)

The required value of x`-=` 239(mod 390)

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes