Results 1 to 2 of 2

Thread: 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 $\displaystyle x$ satisfies $\displaystyle 3x\equiv 6(\bmod 15)$ and $\displaystyle 2x\equiv 10(\bmod 12)$ if and only if $\displaystyle 3x\equiv 6(\bmod 3),3x\equiv 6(\bmod 5), 2x\equiv 10(\bmod 4), 2x\equiv 10(\bmod 3)$.

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

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

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

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

    Therefore, we are left with, $\displaystyle 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 $\displaystyle x\equiv 2(\bmod 3)\text{ and }x\equiv 2(\bmod 5)$ is equivlanet to $\displaystyle x\equiv 2(\bmod 15)$ because $\displaystyle \gcd(3,5)=1$. Thus, we are left with $\displaystyle x\equiv 1(\bmod 2)\text{ and }x\equiv 2(\bmod 15)$. Note that $\displaystyle 17\equiv 1(\bmod 2),17\equiv 2(\bmod 15)$ so we have $\displaystyle x\equiv 17(\bmod 2)\text{ and }x\equiv 17(\bmod 15)$. This combines into $\displaystyle x\equiv 17(\bmod 30)$ since $\displaystyle \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: Jul 15th 2010, 10:26 PM
  2. Working out the mean
    Posted in the Statistics Forum
    Replies: 1
    Last Post: Nov 20th 2009, 10:05 AM
  3. Working with MUnit
    Posted in the Math Software Forum
    Replies: 0
    Last Post: Apr 9th 2009, 03:45 AM
  4. something's not working
    Posted in the Calculus Forum
    Replies: 7
    Last Post: Feb 12th 2009, 04:36 PM
  5. Working Alone
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: Jan 11th 2007, 10:35 PM

Search Tags


/mathhelpforum @mathhelpforum