Polynomials with many roots

**Pn0yS0ld13r** · July 31st 2008, 05:59 PM

I'm having trouble with this one, can anyone give me any hints?

Prove that if $a$ is any integer and the polynomial $f(x) = {x^{2} + ax + 1}$ factors (poly mod 9), then there are three distinct non-negative integers $y$ less than 9 such that $f(y)\equiv 0\bmod{9}$ .

**ThePerfectHacker** · July 31st 2008, 06:21 PM

Originally Posted by Pn0yS0ld13r

I'm having trouble with this one, can anyone give me any hints?

Prove that if $a$ is any integer and the polynomial $f(x) = {x^{2} + ax + 1}$ factors (poly mod 9), then there are three distinct non-negative integers $y$ less than 9 such that $f(y)\equiv 0\bmod{9}$ .

If $x^2+ax+1$ factors then we can write $(x+b)(x+b)$ . Now to have $f(y) \equiv 0 ~ (9)$ we want $(x+b)(x+c) \equiv 0 ~ (9)$ . We can have $x+b\equiv 0 ~ (9)$ as one solution. We also have $x+c \equiv 0 ~ (9)$ as a second solution. But we also have $x+b\equiv 3 ~ (9) \mbox{ and }x+c\equiv 3 ~ (9)$ as a third solution.
Thus, there are at most three solutions. There are not necessarily exactly three solutions. Just consider $a=2$ as a conterexample.

**Pn0yS0ld13r** · July 31st 2008, 07:36 PM

Originally Posted by ThePerfectHacker

But we also have $x+b\equiv 3 ~ (9) \mbox{ and }x+c\equiv 3 ~ (9)$ as a third solution.
Thus, there are at most three solutions.

I'm confused as to how you got the 3's in those congruences.

Originally Posted by ThePerfectHacker

There are not necessarily exactly three solutions. Just consider $a=2$ as a conterexample.

But isin't there still three solutions if $a=2$ ?

i.e., $f(x)={x^{2} + 2x + 1}$ ,
$f(2)\equiv f(5) \equiv f(8) \equiv 0 \bmod{9}$ .

**Moo** · August 1st 2008, 02:10 PM

Hi

Originally Posted by Pn0yS0ld13r

I'm confused as to how you got the 3's in those congruences.

Because 0=9=1*9 (which is equivalent to saying that one of the factors is 0, since 0=9) and also 0=9=3*3.

But isin't there still three solutions if $a=2$ ?

i.e., $f(x)={x^{2} + 2x + 1}$ ,
$f(2)\equiv f(5) \equiv f(8) \equiv 0 \bmod{9}$ .

True.
Like TPH said, if it can be factored, then f(x)=(x+b)(x+c). And we knew from above that there are defined solutions (if we're restricted to the modulus) :
- b=3 mod 9 and c=3 mod 9 : this makes one solution, because b & c have the same modulus
- b=0 mod 9 and then c=1 mod 9 : two solutions

therefore, three distinct solutions

Thread: Polynomials with many roots

LinkBack

Thread Tools

Display

Polynomials with many roots

Similar Math Help Forum Discussions

Roots of 3rd degree polynomials and Characteristic Polynomials

Roots of polynomials

ROOTS and POLYNOMIALS

roots of polynomials

Roots of a sum of polynomials

Search Tags