# A polynomial that factors (poly mod n) but has no roots?

Printable View

• Jul 29th 2008, 12:24 AM
Pn0yS0ld13r
A polynomial that factors (poly mod n) but has no roots?
How is it possible for a polynomial to factor (poly mod n) but have no roots? That is no integers x such that $\displaystyle f(x)\equiv0\bmod{n}$.

Give an example of a polynomial that factors (poly mod n) and prove that it has no roots.

I'm completely stumped. :confused:
• Jul 29th 2008, 12:34 AM
Moo
Hello,
Quote:

Originally Posted by Pn0yS0ld13r
How is it possible for a polynomial to factor (poly mod n) but have no roots? That is no integers x such that $\displaystyle f(x)\equiv0\bmod{n}$.

Give an example of a polynomial that factors (poly mod n) and prove that it has no roots.

I'm completely stumped. :confused:

Here are some examples :
If n=2, in $\displaystyle \bmod 2$, $\displaystyle x^2+x+1$ has no root. (and it's the only one if n=2)

So you can take as an example : $\displaystyle f(x)=(x^2+x+1)^2=x^4+2x^3+3x^2+2x+1 \equiv x^4+x^2+1 \bmod 2$ this factors into $\displaystyle (x^2+x+1) \cdot (x^2+x+1)$ but it has no root $\displaystyle \bmod 2$.

Check it out : $\displaystyle x \equiv 0~,~1~,~2 \bmod 2$ doesn't give any zero for $\displaystyle x^2+x+1$
• Jul 29th 2008, 12:38 AM
Moo
Let's see for $\displaystyle n=3$.

$\displaystyle x^2+1$ has no root $\displaystyle \bmod 3$ (once again, check it out ;))

$\displaystyle x^4+1$ also has no root $\displaystyle \bmod 3$.

Thus $\displaystyle f(x)=(x^2+1) \cdot (x^4+1)=x^6+x^4+x^2+1$ can be factored, but has no root $\displaystyle \bmod 3$

:)