# Polynomtials with multiple roots

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• May 28th 2010, 08: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, 07:21 PM
roninpro
Is there something preventing you from doing either part by force? Just put in every single value of $\displaystyle b$ and see what happens.
• May 29th 2010, 07: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 $\displaystyle 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, 07:30 PM
roninpro
For example, in part one, try $\displaystyle b=0$. Then, we have the polynomial $\displaystyle f(x)=x^2+1$. It does not factor, so we move on. Again, try $\displaystyle b=1$. It does not factor, so move on. Continue this until you reach $\displaystyle b=8$. If your polynomial factors for some $\displaystyle b$, check that it does have three roots.
• May 29th 2010, 07:32 PM
1337h4x
Quote:

Originally Posted by roninpro
For example, in part one, try $\displaystyle b=0$. Then, we have the polynomial $\displaystyle f(x)=x^2+1$. It does not factor, so we move on. Again, try $\displaystyle b=1$. It does not factor, so move on. Continue this until you reach $\displaystyle b=8$. If your polynomial factors for some $\displaystyle 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, 07:34 PM
roninpro
What part of my explanation are you not following?
• May 29th 2010, 07: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, 07:45 PM
roninpro
The question asks you to show that for all $\displaystyle b$, if the polynomial $\displaystyle 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 $\displaystyle 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, 07:46 PM
1337h4x
Quote:

Originally Posted by roninpro
The question asks you to show that for all $\displaystyle b$, if the polynomial $\displaystyle 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 $\displaystyle 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, 12:59 PM
chiph588@
It's safe to assume $\displaystyle b\in\{0,1,2,3,4,5,6,7,8\}$ since we're working modulo $\displaystyle 9$.

roninpro says to just plug each possible value of $\displaystyle b$ into $\displaystyle f(x)$ and see what you get.
• May 30th 2010, 01:26 PM
1337h4x
Quote:

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

roninpro says to just plug each possible value of $\displaystyle b$ into $\displaystyle 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, 01:36 PM
chiph588@
I'll do one for you. Take $\displaystyle b=7$:

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

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

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

We see $\displaystyle x=\{1,4,7\}$ are roots.
• May 30th 2010, 01:56 PM
1337h4x
Quote:

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

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

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

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

We see $\displaystyle 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, 02: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, 02:37 PM
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).
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last