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

Thread: 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 $\displaystyle x^2+bx+1 $ factors modulo $\displaystyle 9 $ i.e. $\displaystyle x^2+bx+1\equiv (x-a)(x-c)\bmod{9} $

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

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

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

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

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

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

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

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

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

    Thus if $\displaystyle x^2+bx+1 $ factors modulo $\displaystyle 9 $ then $\displaystyle 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:

    $\displaystyle 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:

    $\displaystyle 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:

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

    and then how that

    $\displaystyle \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:

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

    and then how that

    $\displaystyle \equiv (x-1)^2 \bmod{9} $
    $\displaystyle -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
    $\displaystyle -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?
    $\displaystyle (x+1)^2\equiv0\bmod{9}\implies 9\mid(x+1)^2\implies3\mid x+1 \implies x+1=3n $

    Now solve $\displaystyle 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
    $\displaystyle (x+1)^2\equiv0\bmod{9}\implies 9\mid(x+1)^2\implies3\mid x+1 \implies x+1=3n $

    Now solve $\displaystyle 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 $\displaystyle (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 $\displaystyle (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 $\displaystyle x^2+bx+1\equiv(x-a)(x-c)\bmod{8} $

    But $\displaystyle (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 $\displaystyle a\equiv a^{-1} \bmod{8} $ for all $\displaystyle a $ with an inverse. Thus we get $\displaystyle 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: Jan 8th 2011, 11:46 AM
  2. multiple roots polynomial
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Oct 28th 2010, 09:24 AM
  3. multiple roots
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Apr 25th 2010, 11:00 AM
  4. Replies: 4
    Last Post: Apr 23rd 2009, 04:59 AM
  5. multiple roots
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Oct 20th 2008, 09:46 PM

Search Tags


/mathhelpforum @mathhelpforum