Results 1 to 6 of 6

Math Help - What am i doing wrong?

  1. #1
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170

    What am i doing wrong?

    Hi,

    Im trying to solve the Congruence system:

    <br />
\begin{cases}<br />
X & \equiv 7 \pmod{17} \\<br />
X & \equiv 9 \pmod{13} \\<br />
X & \equiv 3 \pmod {12} \\<br />
\end{cases}<br />

    My solution looks like this:
    First find u and v such that 17u+13v = 1
    Quickly calculated to be 4*13-3*17 = 1

    Now [LaTeX ERROR: Convert failed]

    Where [LaTeX ERROR: Convert failed]
    This gives [LaTeX ERROR: Convert failed]

    Now we have [LaTeX ERROR: Convert failed]

    Again calculate u and v such that 221u+12v=1
    5*221-92*12 = 1
    [LaTeX ERROR: Convert failed]

    And Finally the general solution is [LaTeX ERROR: Convert failed]

    [LaTeX ERROR: Convert failed]

    But the correct answer, according to the book should be [LaTeX ERROR: Convert failed]

    What am i doing wrong ?
    Last edited by Jones; October 14th 2008 at 07:58 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Jones View Post
    Im trying to solve the Congruence system:

    <br />
\begin{cases}<br />
X & \equiv 7 \pmod{17} \\<br />
X & \equiv 9 \pmod{13} \\<br />
X & \equiv 3 \pmod {12} \\<br />
\end{cases}<br />

    My solution looks like this:
    First find u and v such that 17u+13v = 1
    Quickly calculated to be 4*13-3*17 = 1

    Now \begin{cases}x_{0} & \pmod {17*13} \\ 3 & \pmod {12} \end{cases}

    Where  x_0 = a_2m_1u+a_1m_2v
    This gives  {\color{red}9}*17*4-3*7*13 = 339
    I'm not familiar with that formula for x_0, but it gives the wrong answer: 339 is not congruent to 7 mod 17, nor to 9 mod 13. The smallest number that does have these properties is 126, and the next one is 347.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Quote Originally Posted by Opalg View Post
    I'm not familiar with that formula for x_0, but it gives the wrong answer: 339 is not congruent to 7 mod 17, nor to 9 mod 13. The smallest number that does have these properties is 126, and the next one is 347.
    Hmm, ok.

    How would you do?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    There may be more systematic ways of doing it, but here's how I would go about it.

    We want to solve the congruences \begin{cases}x & \equiv 7\!\!\pmod{17} \\ x& \equiv 9\!\! \pmod{13}\end{cases}. That means that x is a multiple of 17, plus 7; and a multiple of 13, plus 9. Therefore  x = 17p+7=13q+9 (for some integers p and q), from which 13q-17p = 7-9=-2.

    But we know that 13*4 - 17*3=1. Multiply that by -2 to get 13*(-8) - 17*(-6)=-2. Therefore one solution for p and q is q=-8, p=-6. The corresponding value of x is x=-95 (=13*(-8)+9). However, we can add any multiple of 13*17=221 to that, and get another solution for x. It's usually convenient to work with the smallest positive solution, so we'll take x=-95+221=126.

    To complete the solution, we need to solve the congruences  \begin{cases}x&\equiv 126 \!\! \pmod {221} \\ x&\equiv 3 \!\!\pmod {12}\end{cases}. Use the same procedure here. The equations x = 221p + 126 = 12q + 3 tell us that 221p - 12q = 3-126=-123. But we know that 221*5 - 12*92 = 1. Multiply by -123 to get 221*(-615) - 12*(-11316) = -123. So we can take p=-615, giving x=221*(-615)+126=-135789. But we can adjust this by adding any multiple of 12*221=2652, so a better solution would be x=-135789+52*2652=2115.

    That gives the answer you want: z = 2115 + 2652n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Quote Originally Posted by Opalg View Post
    There may be more systematic ways of doing it, but here's how I would go about it.

    We want to solve the congruences \begin{cases}x & \equiv 7\!\!\pmod{17} \\ x& \equiv 9\!\! \pmod{13}\end{cases}. That means that x is a multiple of 17, plus 7; and a multiple of 13, plus 9. Therefore  x = 17p+7=13q+9 (for some integers p and q), from which 13q-17p = 7-9=-2.

    But we know that 13*4 - 17*3=1. Multiply that by -2 to get 13*(-8) - 17*(-6)=-2. Therefore one solution for p and q is q=-8, p=-6. The corresponding value of x is x=-95 (=13*(-8)+9). However, we can add any multiple of 13*17=221 to that, and get another solution for x. It's usually convenient to work with the smallest positive solution, so we'll take x=-95+221=126.

    To complete the solution, we need to solve the congruences  \begin{cases}x&\equiv 126 \!\! \pmod {221} \\ x&\equiv 3 \!\!\pmod {12}\end{cases}. Use the same procedure here. The equations x = 221p + 126 = 12q + 3 tell us that 221p - 12q = 3-126=-123. But we know that 221*5 - 12*92 = 1. Multiply by -123 to get 221*(-615) - 12*(-11316) = -123. So we can take p=-615, giving x=221*(-615)+126=-135789. But we can adjust this by adding any multiple of 12*221=2652, so a better solution would be x=-135789+52*2652=2115.

    That gives the answer you want: z = 2115 + 2652n.
    Thank you sweetheart
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Jones's Avatar
    Joined
    Apr 2006
    From
    Norway
    Posts
    170
    Quote Originally Posted by Opalg View Post
    I'm not familiar with that formula for x_0, but it gives the wrong answer: 339 is not congruent to 7 mod 17, nor to 9 mod 13. The smallest number that does have these properties is 126, and the next one is 347.
    Hi,

    I mixed up the formula. It should be: [Math] 7*13*4-3*9*17[/tex]
    which is -95 \pmod{221} \longrightarrow 126 \pmod{221}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] am I wrong here or is my textbook wrong??
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 25th 2011, 06:13 PM
  2. IVP, what am I doing wrong?
    Posted in the Differential Equations Forum
    Replies: 4
    Last Post: February 10th 2010, 12:17 AM
  3. Replies: 6
    Last Post: August 12th 2009, 03:15 AM
  4. Why am I wrong?!
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 18th 2009, 08:34 PM
  5. Wrong answer key or wrong me ?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: July 2nd 2008, 05:42 AM

Search Tags


/mathhelpforum @mathhelpforum