1. ## 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...

2. 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.

3. 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??

4. 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}$.

5. Thank you!