# 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 $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
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:

$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).

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.

$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.

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

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

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

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

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

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

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

Page 2 of 2 First 12