Register to reply 
Congruence problemby mattmns
Tags: congruence 
Share this thread: 
#1
Oct2305, 08:02 PM

P: 1,123

Hello I have the following question.
 Solve the following congruences simultaneously: [tex]2x + 3y \equiv 2 mod 631[/tex] [tex]3x + 2y \equiv 3 mod 631[/tex]  I first tried adding and got [tex]5x + 5y \equiv 5 mod 631[/tex], but I was then stuck, so I tried the old multiplication, which looked worse as: [tex]6x^2 + 13xy + 6y^2 \equiv 6 mod 631[/tex] 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, [tex]5(x + y) \equiv 5 mod 631[/tex], then find inverse of 5 and multiply it through to find x+y = something mod 631. I did this and got: [tex]x + y \equiv 5*79380 mod 631[/tex] which is [tex]x + y \equiv 1 mod 631[/tex] Now where can I go from here? Any ideas? 


#2
Oct2405, 09:44 AM

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. 


#3
Oct2405, 03:31 PM

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.



#4
Oct2405, 06:42 PM

Emeritus
Sci Advisor
PF Gold
P: 11,155

Congruence problem
No, you won't !
[tex]3x + 2y \equiv 3 ~~(mod~ 631)~~~~(1)[/tex] [tex]2x + 3y \equiv 2 ~~(mod~ 631)~~~~(2)[/tex] Let's do (1)*2  (2)*3 ; this is legal since the modulo is the same for both congruences. [tex]6x + 4y \equiv 6 ~~(mod~ 631)~~~~(3)[/tex] [tex]6x + 9y \equiv 6 ~~(mod~ 631)~~~~(4)[/tex] Subtracting gives : [tex]5y \equiv 0~~ (mod~631) [/tex] What does this tell you about 'y' ? Plug that back in and figure out what 'x' should be. 


#5
Oct2405, 06:50 PM

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!



#6
Oct2405, 07:30 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,323

[tex]2x + 3y \equiv 2 mod 631[/tex]
[tex]3x + 2y \equiv 3 mod 631[/tex] Did you notice that the right hand side is the same as the coefficients of x on the left? Hmm, suppose x= 1? 


Register to reply 
Related Discussions  
Congruence difficulty  Linear & Abstract Algebra  1  
Prove there is at least 1 friday the 13th between march and october  Precalculus Mathematics Homework  3  
Solution to the general congruence  Linear & Abstract Algebra  2  
Congruence problem  Linear & Abstract Algebra  19  
Congruence help  Linear & Abstract Algebra  5 