## Congruence problem

Hello I have the following question.
----
Solve the following congruences simultaneously:

$$2x + 3y \equiv 2 mod 631$$
$$3x + 2y \equiv 3 mod 631$$
----

I first tried adding and got $$5x + 5y \equiv 5 mod 631$$, but I was then stuck, so I tried the old multiplication, which looked worse as: $$6x^2 + 13xy + 6y^2 \equiv 6 mod 631$$

Any ideas? I am guessing that I need to go somewhere with the addition one, but I can't see where. The instructor had a hint of using the fact that 631 is prime, but I can't see anything from that. Thanks.

Hmm, just got an idea, $$5(x + y) \equiv 5 mod 631$$, then find inverse of 5 and multiply it through to find x+y = something mod 631. I did this and got:

$$x + y \equiv 5*79380 mod 631$$
which is
$$x + y \equiv 1 mod 631$$
Now where can I go from here? Any ideas?

 PhysOrg.com science news on PhysOrg.com >> Heat-related deaths in Manhattan projected to rise>> Dire outlook despite global warming 'pause': study>> Sea level influenced tropical climate during the last ice age
 Recognitions: Gold Member Science Advisor Staff Emeritus Try solving them like regular simultaneous equations. Eliminate x from the equations. You have a congruence relation for y. Now plug this back in and find a separate congruence relation for x.
 How would I do that without canceling the y's? In my mind I would have to multiply the top by 3 and bottom by 2, but when I added, I would get 0 = 0 mod 631.

Recognitions:
Gold Member
Staff Emeritus

## Congruence problem

No, you won't !

$$3x + 2y \equiv 3 ~~(mod~ 631)~~~~--(1)$$
$$2x + 3y \equiv 2 ~~(mod~ 631)~~~~--(2)$$

Let's do (1)*2 - (2)*3 ; this is legal since the modulo is the same for both congruences.

$$6x + 4y \equiv 6 ~~(mod~ 631)~~~~--(3)$$
$$6x + 9y \equiv 6 ~~(mod~ 631)~~~~--(4)$$

Subtracting gives : $$5y \equiv 0~~ (mod~631)$$

What does this tell you about 'y' ? Plug that back in and figure out what 'x' should be.

 Wow, I am retarded !!!! Thanks for pointing that out Gokul. Hmm, 3 times 3 is 9, and not 6, interesting! Thanks Gokul!
 Recognitions: Gold Member Science Advisor Staff Emeritus $$2x + 3y \equiv 2 mod 631$$ $$3x + 2y \equiv 3 mod 631$$ Did you notice that the right hand side is the same as the coefficients of x on the left? Hmm, suppose x= 1?

Recognitions:
Gold Member