# Polynomtials with multiple roots

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• May 28th 2010, 09:46 AM
1337h4x
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?
• May 29th 2010, 08:21 PM
roninpro
Is there something preventing you from doing either part by force? Just put in every single value of $b$ and see what happens.
• May 29th 2010, 08:23 PM
1337h4x
Quote:

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.
• May 29th 2010, 08:30 PM
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.
• May 29th 2010, 08:32 PM
1337h4x
Quote:

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 ?
• May 29th 2010, 08:34 PM
roninpro
What part of my explanation are you not following?
• May 29th 2010, 08:39 PM
1337h4x
Quote:

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...
• May 29th 2010, 08:45 PM
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?
• May 29th 2010, 08:46 PM
1337h4x
Quote:

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.
• May 30th 2010, 01:59 PM
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.
• May 30th 2010, 02:26 PM
1337h4x
Quote:

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?
• May 30th 2010, 02:36 PM
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.
• May 30th 2010, 02:56 PM
1337h4x
Quote:

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?
• May 30th 2010, 03:01 PM
chiph588@
Quote:

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?
• May 30th 2010, 03:37 PM
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).
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last