# Solve the system of congruences help?

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!

• Hint: might be easier to write $x \equiv -1$ mod each of $4,5,7$. – 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.

• 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) – CKCMathCS613 Sep 21 '15 at 23:47