Thread: Solving Simultanteous Congruences

Hi:

I'm having some issues trying to figure out how to solve this:



The modulus is 20. So these are equivalent to the congruences:

3x + 5y = 6 (mod 20)
5x + 7y = 14 (mod 20)

which in turn is equivalent to these diophantine equations:

3x + 5y + 20z = 6
5x + 7y + 20z = 14

Now I'm kinda stuck on how to do this. Unless it is valid to subtract the two equations and use the euclidean algorithm on the result??

So
-2x -2y = -8
x + y = 4 and use the euclidean algorithm from here?? Idk any help is much appreciated. There isn't anything remotely close to this in my text...

Why not just use elimination or substitution? From the first equation, you can rearrange to receive . Then, you can put this into the second equation for , or . Now, , so 12 is not invertible. However, you can divide everything by 4 and solve the equation , which gives . Converting back to the original modulus: . Substitute this back into the first equation to get your values.

Good luck.

Thanks. That helps a lot.

Here: 3x + 5y congruent to 6 (mod 20) how did that become x congruent to 2 + 5y (mod 20).Should that not be 3x congruent to 6 - 5y (mod 20)? and how did you get that 6 to 2. You divided by 3 but then why did the 5y not become 5/2? You can't obviously have 5/2y but why did you not divide 5y by 2??

From , you need to solve for , which means removing the 3 coefficient. We need to find the mutliplicative inverse of 3 modulo 20, in this case. If you think about it, . So multiplying both sides by 7 gives .

Thank you!