1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Congruence problem
  1. Quadratic congruence (Replies: 0)

  2. System of congruences (Replies: 9)

Loading...