Congruence problem

by mattmns
Tags: congruence
 Share this thread:
 P: 1,123 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?
 Emeritus Sci Advisor PF Gold P: 11,155 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.
 P: 1,123 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.
 Emeritus Sci Advisor PF Gold P: 11,155 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.
 P: 1,123 Wow, I am retarded !!!! Thanks for pointing that out Gokul. Hmm, 3 times 3 is 9, and not 6, interesting! Thanks Gokul!
 Math Emeritus Sci Advisor Thanks PF Gold P: 39,344 $$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?
Emeritus
Sci Advisor
PF Gold
P: 11,155
 Quote by HallsofIvy Did you notice that the right hand side is the same as the coefficients of x on the left? Hmm, suppose x= 1?
That's the clever way to do it. Us mortals have to turn the cranks....

 Related Discussions Linear & Abstract Algebra 1 Precalculus Mathematics Homework 3 Linear & Abstract Algebra 2 Linear & Abstract Algebra 19 Linear & Abstract Algebra 5