Results 1 to 2 of 2

Math Help - simultaneous congruence that isn't working

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    simultaneous congruence that isn't working

    find a general solution to the simultaneous congruence equations:

    3x congruent to 6 mod 15
    2x congruent to 10 mod 12

    solving the first, 3x = 15t + 6

    i.e. x = 5t + 2

    plugging this into the second, 2(5t + 2) congruent to 10 mod 12

    i.e. 10t congruent to 6 mod 12

    so 10t = 12z + 6

    i.e. 5t = 6z + 3

    so x = 5t + 2 = 6z + 5

    this works for the second, but not the first. What am I doing wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by minivan15 View Post
    find a general solution to the simultaneous congruence equations:

    3x congruent to 6 mod 15
    2x congruent to 10 mod 12
    An integer x satisfies 3x\equiv 6(\bmod 15) and 2x\equiv 10(\bmod 12) if and only if 3x\equiv 6(\bmod 3),3x\equiv 6(\bmod 5), 2x\equiv 10(\bmod 4), 2x\equiv 10(\bmod 3).

    Look at 3x\equiv 6(\bmod 3) first. This is a completely unnecessary congruence because regardless of what x is this congruence always holds, therefore we can throw it away.

    Look at 3x\equiv 6(\bmod 5), since \gcd(3,5)=1 you can divide both sides by 3 to get an equivalent congruence x\equiv 2(\bmod 5).

    Look at 2x\equiv 10(\bmod 4), since \gcd(2,4)=2 and \tfrac{4}{2}=2 we replace it by and equivalent congruence x\equiv 5(\bmod 2) after dividing by 2. This can be further simplifed to the congruence x\equiv 1(\bmod 2).

    Look at 2x\equiv 10(\bmod 3), since \gcd(2,3)=1 we get x\equiv 2(\bmod 3).

    Therefore, we are left with, x\equiv 1(\bmod 2),x\equiv 2(\bmod 3),x\equiv 2(\bmod 5). These congruences now get solved with the Chinese remainder theorem, however I liked to do it without the Chinese remainder theorem, so I show you how I do these sort of problems. Notice that x\equiv 2(\bmod 3)\text{ and }x\equiv 2(\bmod 5) is equivlanet to x\equiv 2(\bmod 15) because \gcd(3,5)=1. Thus, we are left with x\equiv 1(\bmod 2)\text{ and }x\equiv 2(\bmod 15). Note that 17\equiv 1(\bmod 2),17\equiv 2(\bmod 15) so we have x\equiv 17(\bmod 2)\text{ and }x\equiv 17(\bmod 15). This combines into x\equiv 17(\bmod 30) since \gcd(2,15)=1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. check my working
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 15th 2010, 11:26 PM
  2. Working out the mean
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 20th 2009, 11:05 AM
  3. Working with MUnit
    Posted in the Math Software Forum
    Replies: 0
    Last Post: April 9th 2009, 04:45 AM
  4. something's not working
    Posted in the Calculus Forum
    Replies: 7
    Last Post: February 12th 2009, 05:36 PM
  5. Working Alone
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: January 11th 2007, 11:35 PM

Search Tags


/mathhelpforum @mathhelpforum