Results 1 to 3 of 3

Thread: Simultaneous Linear Congruences.

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Simultaneous Linear Congruences.

    I am confused about how I am to solve simultaneous linear congruences, in the book I am reading I am only given 1 example and no general principle.


    Solve

    $\displaystyle x\equiv1\mbox{mod}(4)\ \ \ x\equiv2\mbox{mod}(3)\ \ \ \ x\equiv3\mbox{mod}(5)$

    From the example i think i have to:
    $\displaystyle n_1=4\ \ \ n_2=3\ \ \ \ n_3=5\ \ \ n=60$ and $\displaystyle c_1=15\ \ c_2=20\ \ \ c_3=12$

    and so i have:

    $\displaystyle 15x\equiv1\mbox{mod}(4)\rightarrow{3x\equiv1\mbox{ mod}(4)$
    $\displaystyle 20x\equiv1\mbox{mod}(3)\rightarrow{2x\equiv1\mbox{ mod}(3)$
    $\displaystyle 12x\equiv1\mbox{mod}(5)\rightarrow{2x\equiv1\mbox{ mod}(5)$

    but after this I am lost (im not sure any of that is correct either,

    Thanks very much for any help
    Last edited by hmmmm; Mar 5th 2011 at 06:27 AM. Reason: I wrote the question wrong sorry
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,769
    Thanks
    3027
    Are you sure you have written this correctly? The same x cannot be equivalent to both 1 and 3 modulo 4. That would be like solving a set of simultaneous equations that included both "x= 1" and "x= 3"!

    I will, however, show what I would do if it were, say, $\displaystyle x\equiv 7 (mod 9)$, $\displaystyle x\equiv 3 (mod 5)$ and $\displaystyle x\equiv 1 (mod 4)$ where I have changed the "mod" for one equation.

    Saying that $\displaystyle x\equiv 7 (mod 9)$ means that x= 7+ 9i for any integer i.

    Now put that into the next equation: $\displaystyle x\equiv 3 (mod 5)$ becomes $\displaystyle 7+ 9i\equiv 2+ 4i\equiv 3$ (I have reduced 7 and 9 modulo 5) which is the same as $\displaystyle 4i\equiv 1 (mod 5)$. Since $\displaystyle 4(4)= 16\equiv 1 (mod 5)$, That says that $\displaystyle i\equiv 4 (mod 5)$ so i= 4+ 5j for any integer j. Putting that back into the formula for x, $\displaystyle x= 7+ 9(4+ 5j)= 43+ 45j$.

    Now the third equation, $\displaystyle x\equiv 1 (mod 4)$ becomes $\displaystyle 43+ 45j\equiv 3+ j\equiv 1 (mod 4)$ which is the same as $\displaystyle j\equiv 2 (mod 4)$. And that, in turn gives $\displaystyle j= 2+ 4m$ for any integer m. Putting that into the formula for x, we get $\displaystyle x= 43+ 45(2+ 4m)= 133+ 180m$ as our answer.

    To check, note that 133/9= 14+ 7/9 so x= 133 does satisfy $\displaystyle x\equiv 7 (mod 9)$. 133/5= 26+ 3/5 so x= 133 does satisfy $\displaystyle x\equiv 3 (mod 5)$ and, finally, 133/4= 33+ 1/4 so x= 133 does satisfy $\displaystyle x\equiv 1 (mod 4)$.

    The fact that adding any multiple of 180 to 133 will still give a solution is clear because 180= 9(5)(4) is congruent to 0 mod 9, 5, and 4.
    Last edited by HallsofIvy; Mar 5th 2011 at 06:26 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Dec 2008
    Posts
    288
    You are right i completely messed that question up in asking it I am very sorry it should have been:


    $\displaystyle x\equiv1\mbox{mod}(4)\ \ \ x\equiv2\mbox{mod}(3)\ \ \ \ x\equiv3\mbox{mod}(5)$

    following on from what i have from my textbook i would have that

    $\displaystyle x_0=1.15.3+2.20.2+3.12.2=197mod(60)\equiv17mod(60) )$ but the answer at the back is 57mod(60)

    thanks very much for any help
    Last edited by hmmmm; Mar 5th 2011 at 06:50 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jun 26th 2011, 09:28 PM
  2. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 19th 2009, 08:02 PM
  3. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 19th 2009, 09:33 PM
  4. linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 23rd 2008, 08:27 PM
  5. linear congruences
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Aug 14th 2008, 09:40 AM

Search Tags


/mathhelpforum @mathhelpforum