Results 1 to 5 of 5

Math Help - Solving Simultanteous Congruences

  1. #1
    Newbie chili5's Avatar
    Joined
    Mar 2009
    From
    Canada
    Posts
    17

    Solving Simultanteous Congruences

    Hi:

    I'm having some issues trying to figure out how to solve this:

    <br />
[3][x] + [5][y] = [6]<br />
[5][x] + [7][y] = [14]<br />

    The modulus is 20. So these are equivalent to the congruences:

    3x + 5y = 6 (mod 20)
    5x + 7y = 14 (mod 20)

    which in turn is equivalent to these diophantine equations:

    3x + 5y + 20z = 6
    5x + 7y + 20z = 14

    Now I'm kinda stuck on how to do this. Unless it is valid to subtract the two equations and use the euclidean algorithm on the result??

    So
    -2x -2y = -8
    x + y = 4 and use the euclidean algorithm from here?? Idk any help is much appreciated. There isn't anything remotely close to this in my text...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Why not just use elimination or substitution? From the first equation, you can rearrange to receive x\equiv 5y+2\pmod{20}. Then, you can put this into the second equation for 12y+10\equiv 14\pmod{20}, or 12y\equiv 4\pmod{20}. Now, \gcd(12,20)=4, so 12 is not invertible. However, you can divide everything by 4 and solve the equation 3y\equiv 1\pmod{5}, which gives y\equiv 2\pmod{5}. Converting back to the original modulus: y\equiv 2, 7, 12, 17\pmod{20}. Substitute this back into the first equation to get your x values.

    Good luck.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie chili5's Avatar
    Joined
    Mar 2009
    From
    Canada
    Posts
    17
    Thanks. That helps a lot.

    Here: 3x + 5y congruent to 6 (mod 20) how did that become x congruent to 2 + 5y (mod 20).Should that not be 3x congruent to 6 - 5y (mod 20)? and how did you get that 6 to 2. You divided by 3 but then why did the 5y not become 5/2? You can't obviously have 5/2y but why did you not divide 5y by 2??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    From 3x\equiv 6-5y\pmod{20}, you need to solve for x, which means removing the 3 coefficient. We need to find the mutliplicative inverse of 3 modulo 20, in this case. If you think about it, 3^{-1}\equiv 7\pmod{20}. So multiplying both sides by 7 gives x\equiv 7(6-5y)\equiv 42-35y\equiv 2+5y\pmod{20}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie chili5's Avatar
    Joined
    Mar 2009
    From
    Canada
    Posts
    17
    Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 02:07 AM
  2. solving cubic congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2010, 06:18 AM
  3. Solving linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 12th 2010, 10:46 PM
  4. Solving Congruences
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: August 5th 2009, 10:34 PM
  5. Solving congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 31st 2009, 11:16 PM

Search Tags


/mathhelpforum @mathhelpforum