I am really struggling with how to solve systems of congruences and I have a problem I need to solve as well as some attempt to solve it so any additional help would be so greatly appreciated!

Equations: x = 3 mod 4

x = 4 mod 5

x = 6 mod 7

I started by saying the solution will look like x = 7n + 6 and did the following:

7n+6 = 4mod5

7n = -2mod5

7n = 3mod5

2n = 3mod5

n = (3)(2)n = 3(3) = 9 = 4mod5

so then n = 5k + 4

plug it back in and x = 7(5k+4) +6 = 35k + 34

then plugging that one in to another equation you get

35k + 34 = 3mod4 and 3k = 1mod4

and at this point I just feel completely lost and don't know why I am doing the computations I am doing and where I want to get or anything for that matter.

Any guidance would be super appreciated!

  • $\begingroup$ Hint: might be easier to write $x \equiv -1 $ mod each of $4,5,7$. $\endgroup$ – lulu Sep 21 '15 at 18:59

You are on right track. Now 3k=1 (mod 4), k=3 (mod 4), k=4t+3 for some t. Now substitue it back and you will get x= 140t + 139. Now for any integral value of t ,you will get a solution.

  • $\begingroup$ thanks so much! I was so close, just didn't know how to finish it off. (mainly the dividing 1 by 3 in order to get it in the form k =3mod4 was tripping me up) $\endgroup$ – CKCMathCS613 Sep 21 '15 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.