# Thread: Polynomtials with multiple roots

1. Originally Posted by chiph588@
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).

2. Originally Posted by 1337h4x
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.

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

3. Originally Posted by chiph588@
To find the inverses, use the Euclidean Algorithm, or just guess and check which is what I did.

$\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}$

4. Originally Posted by 1337h4x
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}$

5. Originally Posted by chiph588@
$\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?

6. Originally Posted by 1337h4x
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.

7. Originally Posted by chiph588@
$\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 ?

8. Originally Posted by 1337h4x
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.

9. Originally Posted by chiph588@
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.

10. Originally Posted by 1337h4x
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}$

Page 2 of 2 First 12