Results 1 to 7 of 7

Math Help - Chinese remainder theorem

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Chinese remainder theorem

    Thanks for the wonderful help I've been getting!

    Here is a problem with the Chinese Remainder Theorem:

    x \equiv 1(mod 2)
    x \equiv 2(mod 3)
    x \equiv 3(mod 5)
    x \equiv 4(mod 11)

    x \equiv (1)(165) y_1 + (2)(110) y_2 + (3)(66) y_3 + (4)(30) y_4

    165 \equiv y_1 (mod 2) \Rightarrow y_1 = 1

    110 \equiv y_2 (mod 3) \Rightarrow y_3 = 2

    66 \equiv y_3 (mod 5) \Rightarrow y_3 = 1

    30 \equiv y_4 (mod 11) \Rightarrow y_4 = 7 ??

    I don't understand how the rest of the steps work if now we have to go back and use:
    30 \equiv 8 (mod 11) then 8 y_4 \equiv 1 (mod 11)?

    I thought I had finally comprehended Euclidean Algorithm with inverses, but now I'm not so sure.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by oldguynewstudent View Post
    Thanks for the wonderful help I've been getting!

    Here is a problem with the Chinese Remainder Theorem:

    x \equiv 1(mod 2)
    x \equiv 2(mod 3)
    x \equiv 3(mod 5)
    x \equiv 4(mod 11)

    x \equiv (1)(165) y_1 + (2)(110) y_2 + (3)(66) y_3 + (4)(30) y_4

    165 \equiv y_1 (mod 2) \Rightarrow y_1 = 1

    110 \equiv y_2 (mod 3) \Rightarrow y_3 = 2

    66 \equiv y_3 (mod 5) \Rightarrow y_3 = 1

    30 \equiv y_4 (mod 11) \Rightarrow y_4 = 7 ??

    I don't understand how the rest of the steps work if now we have to go back and use:
    30 \equiv 8 (mod 11) then 8 y_4 \equiv 1 (mod 11)?

    I thought I had finally comprehended Euclidean Algorithm with inverses, but now I'm not so sure.
    I'm not sure what's your problem: you got y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7 \Longrightarrow\,x=165\cdot 1+220\cdot 2+198\cdot 1+120\cdot 7=1,643.

    What do you mean "go back", anyway? Go back where and what for?

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    I was missing a step

    Quote Originally Posted by tonio View Post
    I'm not sure what's your problem: you got y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7 \Longrightarrow\,x=165\cdot 1+220\cdot 2+198\cdot 1+120\cdot 7=1,643.

    What do you mean "go back", anyway? Go back where and what for?

    Tonio
    I was missing a step or I had the next to last step incorrect.

    I found out in class last night that I should have had the following:

    165 y_1 \equiv 1(mod 2) \Rightarrow y_1 = 1

    110 y_2 \equiv 1(mod 3) \Rightarrow y_2 = 2

    66 y_3 \equiv 1(mod 5) \Rightarrow y_3 = 1

    30 y_4 \equiv 1(mod 11) \Rightarrow y_4 = 7

    Substituting in the above equation gives x = 1643 \equiv 323(mod 330)

    So x = 323 + 330k where k is an element Z
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Chinese Remainder Theorem

    Hello oldguynewstudent
    Quote Originally Posted by oldguynewstudent View Post
    Thanks for the wonderful help I've been getting!

    Here is a problem with the Chinese Remainder Theorem:

    x \equiv 1(mod 2)
    x \equiv 2(mod 3)
    x \equiv 3(mod 5)
    x \equiv 4(mod 11)

    x \equiv (1)(165) y_1 + (2)(110) y_2 + (3)(66) y_3 + (4)(30) y_4

    165 \equiv y_1 (mod 2) \Rightarrow y_1 = 1

    110 \equiv y_2 (mod 3) \Rightarrow y_3 = 2

    66 \equiv y_3 (mod 5) \Rightarrow y_3 = 1

    30 \equiv y_4 (mod 11) \Rightarrow y_4 = 7 ??

    I don't understand how the rest of the steps work if now we have to go back and use:
    30 \equiv 8 (mod 11) then 8 y_4 \equiv 1 (mod 11)?

    I thought I had finally comprehended Euclidean Algorithm with inverses, but now I'm not so sure.
    Hold on here, I think you've oversimplified things! Perhaps you realised that things weren't right because 30\equiv 8 \mod 11, and you needed 30\equiv 7 \mod 11 to get the right answer! Hence the question mark in your solution.

    I'm afraid the method is a little bit more complicated than your answer.

    Let me try and spell it out for you.

    First, let me repeat the correct start you made: we need to find 4 numbers y_1 ... y_4, and then find x by saying:
    x = 1.165y_1+2.110y_2+3.66y_3+4.30y_4
    where:
    1, 2, 3, 4 are the modular equivalents of x (mods 2, 3, 5, 11) in the four original equations;
    and the numbers
    165, 110, 66, 30 are quotients when the product of the four moduli, 2\times3\times5\times11, is divided in turn by 2, 3, 5, 11.
    So far, so good.

    So how do we find the y_i? The answer is by solving a set of equations of the form a_in_i + b_iy_i = 1, by using the Euclidean Algorithm. In each case:
    a_i is the modulus of the equation: 2, 3, 5, 11

    b_i is the corresponding quotient 165, 110, 66, 30
    So we get:

    For y_1: solve the equation 2n_1 + 165y_1=1. This gives n_1=-82, y_1=1

    For y_2: solve 3n_2+110y_2=1. This gives n_2=37, y_2 = -1 (which is equivalent to y_2 = 2 as you had)

    For y_3: 5n_3+66y_3 = 1\Rightarrow n_3 =-13, y_3=1

    For y_4, let me do the working in full, using the Euclidean Algorithm. We need to solve:
    11n_4+30y_4 = 1
    So we say:
    30 = 2\times11+8
    11=1\times8+3
    8=2\times3+2
     3=2+1
    Then we 'go back' (perhaps this is what you meant):
    1=3-2
     =3-(8-2\times3)
     =3\times3-8
     =3\times(11-8)-8
     =3\times11-4\times8
     =3\times11-4(30-2\times11)
     =11\times11-4\times30
     \Rightarrow n_4=11, y_4 = -4
    Finally, we use these four values of y_i to calculate x:
    x=1\times165-2\times110+3\times66-120\times4=-337
    If you don't like this answer, and would like something a bit more positive, you can add on as many 330's ( =2\times3\times5\times11) as you like. The smallest positive value of x, then, is -337+2\times330 =323; and to get the solution which (by chance!) you found, add 6\times 330 = 1980 to get 1643.

    Grandad
    Last edited by Grandad; November 18th 2009 at 02:45 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Aha

    As Ricky said to Lucy, "That 'splains it!"
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2008
    From
    Berkeley, Illinois
    Posts
    364
    Quote Originally Posted by Grandad View Post

    For y_2: solve 3n_2+110y_2=1. This gives n_2=37, y_2 = -1 (which is equivalent to y_2 = 2 as you had)
    Grandad,

    Why if we get a negative answer for y2, do we need to make it 2?

    Is there something in the theorem that states it needs to be positive?

    How did you get from -1 to 2?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello mathceleb
    Quote Originally Posted by mathceleb View Post
    Grandad,

    Why if we get a negative answer for y2, do we need to make it 2?

    Is there something in the theorem that states it needs to be positive?

    How did you get from -1 to 2?
    You're asking 3 questions here.

    Why do we need to make y_2 = 2? We don't. -1 works just as well. See below.

    Does it need to be positive? No. You'll see that I used 2 negative values ( y_2=-1 and y_4 = -4) in my final evaluation of x. These were the ones I got by using the Euclidean Algorithm to solve the equations. This gave me the value x = -337, which is a perfectly good solution. Try it - you'll find it satisfies all four of the original modular equations.

    As I then explained, you can add on any multiple of 330 to obtain further, equally valid, values of x. In general, then, any value given by x = -337 + 330n will work.

    How did I get from -1 to 2? It may sound trivial, but I added 3. Why?

    y_2=-1, n_2 = 37 was a solution to the equation:
    3n_2+110y_2=1
    which again I found using the Euclidean Algorithm. But, since this is simply a solution to the modular equation
    110y_2\equiv 1\mod 3
    any value of y_2 that is equivalent to -1 \mod 3 will do equally well. So that's 2, 5, 8, ..., -4, -7, ... and so on. Each different value of y_2 will have a different value of n_2 (for example, y_2=2 will require n_2 = -73), but any one of these could be used in the final calculation of x.

    Can you see why? It's because in the formula for x, y_2 is multiplied by 220. So two values of y_2 that differ by 3 will result in a value of x that differs by 660, and as we've seen, that will work just as well.

    I hope that helps to clarify things.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 10th 2010, 01:24 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 07:56 PM
  3. Chinese remainder theorem 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 19th 2009, 10:38 AM
  4. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 24th 2009, 11:19 AM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum