# Thread: Polynomtials with multiple roots

1. ## Polynomtials with multiple roots

Hello All,

My book states the following:

[PART ONE]

If 'b' is any integer and the polynomial f(x)=(x^2)+bx+1 factors (poly mod 9), there exists 3 distinct non-negative integers 'q' less than than 9 so that f(q) = 0(mod 9).

How can this be proven?

[PART TWO]

If 'b' is any integer and the polynomial f(x)=(x^2)+bx+1 factors (poly mod 8), then f(x) is a square. E.g. f(x) = ((x+c)^2)(poly mod 8) where 0<c<8.

Can anyone think of values of b that makes this possible?

2. Is there something preventing you from doing either part by force? Just put in every single value of $b$ and see what happens.

3. Originally Posted by roninpro
Is there something preventing you from doing either part by force? Just put in every single value of $b$ and see what happens.
I don't know what you mean. I have tried a couple different approaches but haven't gotten anywhere. That's why I'm asking for help and some guidance.

4. For example, in part one, try $b=0$. Then, we have the polynomial $f(x)=x^2+1$. It does not factor, so we move on. Again, try $b=1$. It does not factor, so move on. Continue this until you reach $b=8$. If your polynomial factors for some $b$, check that it does have three roots.

5. Originally Posted by roninpro
For example, in part one, try $b=0$. Then, we have the polynomial $f(x)=x^2+1$. It does not factor, so we move on. Again, try $b=1$. It does not factor, so move on. Continue this until you reach $b=8$. If your polynomial factors for some $b$, check that it does have three roots.
Sorry, I'm not following how that will help me with either my 1st or 2nd question. Could someone be more direct ?

6. What part of my explanation are you not following?

7. Originally Posted by roninpro
What part of my explanation are you not following?

Well what values can you get for the second one to prove it? I can't find any...

8. The question asks you to show that for all $b$, if the polynomial $x^2+bx+1$ factors, then it has a certain number of roots. Since we are working modulo 8 or 9, we can just check every single value of $b$ and see if the result is true. (There are only finitely many values.)

Are you having a problem with factoring or finding roots of polynomials?

9. Originally Posted by roninpro
The question asks you to show that for all $b$, if the polynomial $x^2+bx+1$ factors, then it has a certain number of roots. Since we are working modulo 8 or 9, we can just check every single value of $b$ and see if the result is true. (There are only finitely many values.)

Are you having a problem with factoring or finding roots of polynomials?
I brute force it for the FIRST question and all i get is for b=2 i get (x+1)(x+1), but that's it.

I still don't understand the SECOND question at all.

10. It's safe to assume $b\in\{0,1,2,3,4,5,6,7,8\}$ since we're working modulo $9$.

roninpro says to just plug each possible value of $b$ into $f(x)$ and see what you get.

11. Originally Posted by chiph588@
It's safe to assume $b\in\{0,1,2,3,4,5,6,7,8\}$ since we're working modulo $9$.

roninpro says to just plug each possible value of $b$ into $f(x)$ and see what you get.
I did but the only one that factored was when b=2 which factored into (x+1)^2 but I don't see how that will help me considering that I know only 1 distinct root. Is this even right or am I doing something wrong? What other ones exist?

12. I'll do one for you. Take $b=7$:

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

So $f(x)\equiv(x-1)^2\bmod{9}$

Now solve $(x-1)^2\equiv0\bmod{9}$

We see $x=\{1,4,7\}$ are roots.

13. Originally Posted by chiph588@
I'll do one for you. Take $b=7$:

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

So $f(x)\equiv(x-1)^2\bmod{9}$

Now solve $(x-1)^2\equiv0\bmod{9}$

We see $x=\{1,4,7\}$ are roots.
So are 1,4,7 the 3 distinct roots? How did you get them? I just need to see one of those conversions like what you did for b = 7. How did you change that over to a mod 9?

14. Originally Posted by 1337h4x
So are 1,4,7 the 3 distinct roots? How did you get them? I just need to see one of those conversions like what you did for b = 7. How did you change that over to a mod 9?
what?

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

Page 1 of 2 12 Last