Solving Simultanteous Congruences

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

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

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

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