Results 1 to 3 of 3

Math Help - 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

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

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

    and so i have:

     15x\equiv1\mbox{mod}(4)\rightarrow{3x\equiv1\mbox{  mod}(4)
    20x\equiv1\mbox{mod}(3)\rightarrow{2x\equiv1\mbox{  mod}(3)
    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; March 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
    15,696
    Thanks
    1467
    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, x\equiv 7 (mod 9), x\equiv 3 (mod 5) and x\equiv 1 (mod 4) where I have changed the "mod" for one equation.

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

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

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

    To check, note that 133/9= 14+ 7/9 so x= 133 does satisfy x\equiv 7 (mod 9). 133/5= 26+ 3/5 so x= 133 does satisfy x\equiv 3 (mod 5) and, finally, 133/4= 33+ 1/4 so x= 133 does satisfy 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; March 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:


    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

     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; March 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: June 26th 2011, 09:28 PM
  2. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 19th 2009, 08:02 PM
  3. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 19th 2009, 09:33 PM
  4. linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2008, 08:27 PM
  5. linear congruences
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 14th 2008, 09:40 AM

Search Tags


/mathhelpforum @mathhelpforum