Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Congruence problem

  1. Oct 23, 2005 #1
    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. jcsd
  3. Oct 24, 2005 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. Oct 24, 2005 #3
    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.
     
  5. Oct 24, 2005 #4

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  6. Oct 24, 2005 #5
    Wow, I am retarded :rofl: !!!! Thanks for pointing that out Gokul. Hmm, 3 times 3 is 9, and not 6, interesting! :rofl: Thanks Gokul!
     
  7. Oct 24, 2005 #6

    HallsofIvy

    User Avatar
    Science Advisor

    [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?
     
  8. Oct 25, 2005 #7

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's the clever way to do it. Us mortals have to turn the cranks.... :biggrin:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook