Page 2 of 2 FirstFirst 12
Results 16 to 25 of 25

Math Help - Polynomtials with multiple roots

  1. #16
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    Since you don't get what we're saying, let me try a different approach.

    We're given  x^2+bx+1 factors modulo  9 i.e.  x^2+bx+1\equiv (x-a)(x-c)\bmod{9}

    But  (x-a)(x-c)=x^2-(a+c)x+ac\equiv x^2+bx+1\bmod{9}

    So  ac\equiv1\bmod{9}\implies c\equiv a^{-1}\bmod{9}

    We then get  x^2+bx+1\equiv x^2-(a+a^{-1})x+1\bmod{9} for some  a that has an inverse modulo  9 .

    Here's all  a with an inverse:
    \begin{tabular}{c | c}\hline<br />
      a & a inverse\\\hline<br />
      1 & 1 \\<br />
      2 & 5 \\<br />
      4 & 7 \\<br />
      5 & 2 \\<br />
      7 & 4 \\<br />
      8 & 8 \\\hline<br />
      \end{tabular}

    Looking at the table we see there are four cases to consider:

    a=1:  f(x)\equiv x^2-(1+1)x+1\equiv(x-1)^2 \bmod{9}

    a=2:  f(x)\equiv x^2-(2+5)x+1\equiv(x+1)^2 \bmod{9}

    a=4:  f(x)\equiv x^2-(4+7)x+1\equiv(x-1)^2 \bmod{9}

    a=8:  f(x)\equiv x^2-(8+8)x+1\equiv(x+1)^2 \bmod{9}

    Thus if  x^2+bx+1 factors modulo  9 then  f(x)\equiv (x\pm1)^2\bmod{9} . Now check to see there are three roots for both cases (this should be very easy).

    Can you explain how you came up with the chart? I can track you all the way up to there. After you came up with the inverses, I see how you plugged in the numbers with a and a inverse, but I don't see how you formed the right hand side statements (which yielded +-1 roots).
    Follow Math Help Forum on Facebook and Google+

  2. #17
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    Can you explain how you came up with the chart? I can track you all the way up to there. After you came up with the inverses, I see how you plugged in the numbers with a and a inverse, but I don't see how you formed the right hand side statements (which yielded +-1 roots).
    To find the inverses, use the Euclidean Algorithm, or just guess and check which is what I did.

    For your other question:

     f(x)\equiv x^2-(4+7)x+1=x^2-11x+1\equiv x^2-2x+1=(x-1)^2 \bmod{9}
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    To find the inverses, use the Euclidean Algorithm, or just guess and check which is what I did.

    For your other question:

     f(x)\equiv x^2-(4+7)x+1=x^2-11x+1\equiv x^2-2x+1=(x-1)^2 \bmod{9}
    Can you explain just this:

     x^2-11x+1\equiv x^2-2x+1

    and then how that

     \equiv (x-1)^2 \bmod{9}
    Follow Math Help Forum on Facebook and Google+

  4. #19
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    Can you explain just this:

     x^2-11x+1\equiv x^2-2x+1

    and then how that

     \equiv (x-1)^2 \bmod{9}
     -11\equiv-2\bmod{9}\implies x^2-11x+1\equiv x^2-2x+1\bmod{9}
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
     -11\equiv-2\bmod{9}\implies x^2-11x+1\equiv x^2-2x+1\bmod{9}
    So when you are referring to finding 3 roots for "both" cases, I have this so far:

    Case 1: (x^2)+2x+1 mod 9 ? roots = ? without the mod 9 I have (x+1)(x+1)...
    Case 2: (x^2)-2x+1 mod 9 ? roots = ? without the mod 9 I have (x-1)(x-1)...

    So I have 2 roots for each case of +1 -1 which is what I started with... Where am I going wrong?
    Follow Math Help Forum on Facebook and Google+

  6. #21
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    So when you are referring to finding 3 roots for "both" cases, I have this so far:

    Case 1: (x^2)+2x+1 mod 9 ? roots = ? without the mod 9 I have (x+1)(x+1)...
    Case 2: (x^2)-2x+1 mod 9 ? roots = ? without the mod 9 I have (x-1)(x-1)...

    So I have 2 roots for each case of +1 -1 which is what I started with... Where am I going wrong?
     (x+1)^2\equiv0\bmod{9}\implies 9\mid(x+1)^2\implies3\mid x+1 \implies x+1=3n

    Now solve  x+1=3,\; x+1=3\cdot2,\; x+1=3\cdot3 and we've found our roots.
    Follow Math Help Forum on Facebook and Google+

  7. #22
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
     (x+1)^2\equiv0\bmod{9}\implies 9\mid(x+1)^2\implies3\mid x+1 \implies x+1=3n

    Now solve  x+1=3,\; x+1=3\cdot2,\; x+1=3\cdot3 and we've found our roots.
    So the roots are x = 2, 5, 8 ?
    Follow Math Help Forum on Facebook and Google+

  8. #23
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    So the roots are x = 2, 5, 8 ?
    Yes, now do the same for  (x-1)^2 and you're done with the first part.

    Next try the second part of the original question on your own.
    Follow Math Help Forum on Facebook and Google+

  9. #24
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    Yes, now do the same for  (x-1)^2 and you're done with the first part.

    Next try the second part of the original question on your own.

    So for (x-1)^2 case we get x = 4, 7, and 10 ?

    And how do I prove my second question? It has that part about squares in it.
    Follow Math Help Forum on Facebook and Google+

  10. #25
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    So for (x-1)^2 case we get x = 4, 7, and 10 ?

    And how do I prove my second question? It has that part about squares in it.
    Yes except take 10 mod 9 to get x=1.

    Again assume x^2+bx+1 factors mod 8

    So  x^2+bx+1\equiv(x-a)(x-c)\bmod{8}

    But  (x-a)(x-c)=x^2-(a+c)x+ac\implies ac\equiv1\bmod{8}\implies c\equiv a^{-1} \bmod{8}

    Now verify that  a\equiv a^{-1} \bmod{8} for all  a with an inverse. Thus we get  x^2+bx+1\equiv(x-a)(x-c)\equiv(x-a)(x-a^{-1})\equiv(x-a)(x-a)=(x-a)^2\bmod{8}
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. No multiple roots in R
    Posted in the Advanced Algebra Forum
    Replies: 12
    Last Post: January 8th 2011, 11:46 AM
  2. multiple roots polynomial
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 28th 2010, 09:24 AM
  3. multiple roots
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 25th 2010, 11:00 AM
  4. Replies: 4
    Last Post: April 23rd 2009, 04:59 AM
  5. multiple roots
    Posted in the Algebra Forum
    Replies: 2
    Last Post: October 20th 2008, 09:46 PM

Search Tags


/mathhelpforum @mathhelpforum