Results 1 to 7 of 7

Thread: Chinese remainder theorem

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

    Chinese remainder theorem

    Thanks for the wonderful help I've been getting!

    Here is a problem with the Chinese Remainder Theorem:

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

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

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

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

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

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

    I don't understand how the rest of the steps work if now we have to go back and use:
    30 $\displaystyle \equiv$ 8 (mod 11) then 8$\displaystyle y_4$ $\displaystyle \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
    3
    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 $\displaystyle \equiv$ 1(mod 2)
    x $\displaystyle \equiv$ 2(mod 3)
    x $\displaystyle \equiv$ 3(mod 5)
    x $\displaystyle \equiv$ 4(mod 11)

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

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

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

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

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

    I don't understand how the rest of the steps work if now we have to go back and use:
    30 $\displaystyle \equiv$ 8 (mod 11) then 8$\displaystyle y_4$ $\displaystyle \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 $\displaystyle y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7$ $\displaystyle \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
    Senior Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    255

    I was missing a step

    Quote Originally Posted by tonio View Post
    I'm not sure what's your problem: you got $\displaystyle y_1=1\,,\,y_2=2\,,\,y_3=1\,,\,y_4=7$ $\displaystyle \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$\displaystyle y_1$ $\displaystyle \equiv$ 1(mod 2) $\displaystyle \Rightarrow$ $\displaystyle y_1$ = 1

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

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

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

    Substituting in the above equation gives x = 1643 $\displaystyle \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 $\displaystyle \equiv$ 1(mod 2)
    x $\displaystyle \equiv$ 2(mod 3)
    x $\displaystyle \equiv$ 3(mod 5)
    x $\displaystyle \equiv$ 4(mod 11)

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

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

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

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

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

    I don't understand how the rest of the steps work if now we have to go back and use:
    30 $\displaystyle \equiv$ 8 (mod 11) then 8$\displaystyle y_4$ $\displaystyle \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 $\displaystyle 30\equiv 8 \mod 11$, and you needed $\displaystyle 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 $\displaystyle 4$ numbers $\displaystyle y_1 ... y_4$, and then find $\displaystyle x$ by saying:
    $\displaystyle x = 1.165y_1+2.110y_2+3.66y_3+4.30y_4$
    where:
    $\displaystyle 1, 2, 3, 4$ are the modular equivalents of $\displaystyle x$ (mods $\displaystyle 2, 3, 5, 11$) in the four original equations;
    and the numbers
    $\displaystyle 165, 110, 66, 30$ are quotients when the product of the four moduli, $\displaystyle 2\times3\times5\times11$, is divided in turn by $\displaystyle 2, 3, 5, 11$.
    So far, so good.

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

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

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

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

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

    For $\displaystyle y_4$, let me do the working in full, using the Euclidean Algorithm. We need to solve:
    $\displaystyle 11n_4+30y_4 = 1$
    So we say:
    $\displaystyle 30 = 2\times11+8$
    $\displaystyle 11=1\times8+3$
    $\displaystyle 8=2\times3+2$
    $\displaystyle 3=2+1$
    Then we 'go back' (perhaps this is what you meant):
    $\displaystyle 1=3-2$
    $\displaystyle =3-(8-2\times3)$
    $\displaystyle =3\times3-8$
    $\displaystyle =3\times(11-8)-8$
    $\displaystyle =3\times11-4\times8$
    $\displaystyle =3\times11-4(30-2\times11)$
    $\displaystyle =11\times11-4\times30$
    $\displaystyle \Rightarrow n_4=11, y_4 = -4$
    Finally, we use these four values of $\displaystyle y_i$ to calculate $\displaystyle x$:
    $\displaystyle 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 $\displaystyle 330$'s ($\displaystyle =2\times3\times5\times11$) as you like. The smallest positive value of $\displaystyle x$, then, is $\displaystyle -337+2\times330 =323$; and to get the solution which (by chance!) you found, add $\displaystyle 6\times 330 = 1980$ to get $\displaystyle 1643$.

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

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

    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
    377
    Thanks
    1
    Quote Originally Posted by Grandad View Post

    For $\displaystyle y_2$: solve $\displaystyle 3n_2+110y_2=1$. This gives $\displaystyle n_2=37, y_2 = -1$ (which is equivalent to $\displaystyle 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 $\displaystyle y_2 = 2$? We don't. $\displaystyle -1$ works just as well. See below.

    Does it need to be positive? No. You'll see that I used $\displaystyle 2$ negative values ($\displaystyle y_2=-1$ and $\displaystyle y_4 = -4$) in my final evaluation of $\displaystyle x$. These were the ones I got by using the Euclidean Algorithm to solve the equations. This gave me the value $\displaystyle 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 $\displaystyle 330$ to obtain further, equally valid, values of $\displaystyle x$. In general, then, any value given by $\displaystyle x = -337 + 330n$ will work.

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

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

    Can you see why? It's because in the formula for $\displaystyle x, y_2$ is multiplied by $\displaystyle 220$. So two values of $\displaystyle y_2$ that differ by $\displaystyle 3$ will result in a value of $\displaystyle x$ that differs by $\displaystyle 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: Feb 25th 2010, 07:56 PM
  3. Chinese remainder theorem 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 19th 2009, 10:38 AM
  4. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jun 24th 2009, 11:19 AM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum