# Solving Simultanteous Congruences

• Nov 7th 2010, 08:41 AM
chili5
Solving Simultanteous Congruences
Hi:

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

$
[3][x] + [5][y] = [6]
[5][x] + [7][y] = [14]
$

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...
• Nov 7th 2010, 10:15 AM
roninpro
Why not just use elimination or substitution? From the first equation, you can rearrange to receive $x\equiv 5y+2\pmod{20}$. Then, you can put this into the second equation for $12y+10\equiv 14\pmod{20}$, or $12y\equiv 4\pmod{20}$. Now, $\gcd(12,20)=4$, so 12 is not invertible. However, you can divide everything by 4 and solve the equation $3y\equiv 1\pmod{5}$, which gives $y\equiv 2\pmod{5}$. Converting back to the original modulus: $y\equiv 2, 7, 12, 17\pmod{20}$. Substitute this back into the first equation to get your $x$ values.

Good luck.
• Nov 7th 2010, 10:35 AM
chili5
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??
• Nov 7th 2010, 12:33 PM
roninpro
From $3x\equiv 6-5y\pmod{20}$, you need to solve for $x$, 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, $3^{-1}\equiv 7\pmod{20}$. So multiplying both sides by 7 gives $x\equiv 7(6-5y)\equiv 42-35y\equiv 2+5y\pmod{20}$.
• Nov 7th 2010, 04:05 PM
chili5
Thank you! :D