# Thread: Polynomials with many roots

1. ## Polynomials with many roots

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

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

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

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