# Does $f(x) \in \mathbb{Z}[x] \$ have the same roots as $f(x) \in \mathbb{F}_p[x] \quad$?

Does $f(x)\in\mathbb{Z}[x]\$ have the same roots of $f(x)\in\mathbb{F}_p[x] \quad$?

Do the roots of a polynomial change when the coefficients of the polynomial are considered as elements of one ring or another? Would the answer to this change if the rings contained each other, as in the case of $f(x) \in \mathbb{Z}[x] \ \$ vs. $\ f(x) \in \mathbb{Q}[x] \quad$?

-

Short answer: Yes, the set of roots can change. $f(x)=x^2+1$ has no roots in $\mathbb{Z}$, but (the image of $f(x)$ under reduction modulo $p$) has roots in $\mathbb{F}_p$ if $p=2$ or $p\equiv 1 \pmod{4}$.

Longer answer: First, you have to be careful. If $f(x)$ is a polynomial with integer coefficients, then it is not literally a polynomial with coefficients in $\mathbb{F}_p$. Rather, the natural map "reduction modulo $p$", which is a ring map from $\mathbb{Z}$ to $\mathbb{F}_p$, induces a map from $\mathbb{Z}[x]$ to $\mathbb{F}_p[x]$, and you can consider the image of $f(x)$ in $\mathbb{F}_p[x]$.

Under this map, if $a\in\mathbb{Z}$ is a root of $f(x)$, then $a\bmod p$ is a root of $f(x)\bmod p$ in $\mathbb{F}_p[x]$. But the converse certainly does not hold; for one thing, there are infinitely many integers that are preimages of $a\bmod p$. And for another, no: you can have $f(x)\bmod p$ have roots in $\mathbb{F}_p[x]$, but no roots in $\mathbb{Z}[x]$, or only some roots. For example, for odd primes $p$, $f(x) = x^{p}-x$ has only two roots in $\mathbb{Z}$ ($x=0$ and $x=1$), but (its image under reduction modulo $p$) has $p$ roots in $\mathbb{F}_p$. So roots in $\mathbb{Z}$ yield roots in $\mathbb{F}_p$ (via reduction modulo $p$), but not conversely. Another example: $x^2+1$ has no roots in $\mathbb{Z}$, but (its reduction modulo $p$) has roots in $\mathbb{F}_p$ for every $p$ that is not congruent to $3$ modulo $4$.

More generally, the universal property of the polynomial ring gives easily:

Theorem. Let $R$ and $S$ be commutative rings. If $h\colon R\to S$ is a ring homomorphism, then $h$ induces a ring homomorphism $\overline{h}\colon R[x]\to S[x]$ of polynomial rings by $$\overline{h}(r_0+r_1x + \cdots + r_nx^n) = h(r_0) + h(r_1)x + \cdots + h(r_n)x^n.$$ Moreover, the map $\overline{h}$ commutes with evaluation maps in the following sense: if $\mathrm{eval}_a\colon R[x]\to R$ is the map $\mathrm{eval}_a(f(x)) = f(a)$, and $\mathrm{eval}_{h(a)}\colon S[x]\to S$ is the evaluation map at $h(a)$, then we have a commutative diagram $$\begin{array}{rcl} R[x] & \stackrel{\overline{h}}{\longmapsto} & S[x]\\ &&\\ \mathrm{eval}_a\downarrow & & \downarrow \mathrm{eval}_{h(a)}\\ R &\stackrel{h}{\longmapsto} & S\end{array}$$ for all $a\in R$.

In particular, if given $f\in R[x]$ and $g\in S[x]$ we let $$\mathrm{Roots}_R(f) = \{r\in R\mid f(r)=0\}$$ and $$\mathrm{Roots}_S(g) = \{s \in S\mid g(s)=0\},$$ then $$h\left(\mathrm{Roots}_R(f)\right) \subseteq \mathrm{Roots}_S(\overline{h}(f)),$$ but the inclusion may be proper.

For examples with proper inclusion in the setting of reduction modulo $p$, consider $f(x)=x^2+1\in\mathbb{Z}[x]$ which has not roots, but whose reduction modulo $p$, with $p=2$ or $p\equiv 1\pmod{4}$ has roots. Or $f(x)=x^p-x$, $p$ an odd prime, which has two roots in $\mathbb{Z}$ but its reduction modulo $p$ has $p$ roots in $\mathbb{F}_p$ (by Fermat's Little Theorem). For examples of proper inclusion with fields and $h$ an inclusion map, take $x^2+1\in\mathbb{R}[x]$, and consider its image in $\mathbb{C}[x]$; $x^2+1$ has no real roots, but its image in $\mathbb{C}[x]$ has roots.

Added. When dealing with inclusion, it usually makes more sense to consider the set of roots in the larger field, and just ask which ones lie in the smaller field. So we think of $x^2+1$ as a polynomial with complex coefficients, and then ask what $\mathrm{Roots}_{\mathbb{C}}(x^2+1)\cap\mathbb{R}$ is (this will equal $\mathrm{Roots}_{\mathbb{R}}(x^2+1)$).

Also, if $h(a)$, the image of $a$ is a root of $\overline{h}(f)$, this does not imply, in and of itself, that $a$ is a root of $f(x)$ (though it does if $h$ is one-to-one).

To summarize the longer answer: if $h\colon R\to S$ is a ring homomorphism, then the image of any root of $f(x)$ is a root of the image of $f(x)$, but there may be roots of the image that are not images of roots; and not everything in $R$ whose image is a root of the image of $f(x)$ is a root of $f(x)$ in general. But if $h$ is one-to-one, then $h(a)$ is a root of $\overline{h}(f(x))$ if and only if $a$ is a root of $f(x)$.

-
Holy crap, you wrote a book for me. Thanks, I appreciate it :) – badatmath Apr 26 '11 at 4:29
Hello, and thanks :) I guess I am confused because when you talk about polynomials like $x^2+1$ with coefficients in $\mathbb{Z}[x]$, you say this polynomial has roots, but its roots are in $\mathbb{C}$. If you say $x^2+1$ has coefficients in $\mathbb{F}_p[x]$, can you also say this polynomial has roots in $\mathbb{C}$? Does it make a difference that $\mathbb{C}$ does not contain $\mathbb{F}_p$? – badatmath Apr 26 '11 at 4:32
@badatmath: I did not say "the roots are in $\mathbb{C}$." The inclusion $\mathbb{Z}\hookrightarrow\mathbb{C}$ means you can consider polynomials with integer coefficients as polynomials with complex coefficients. If you do that, then the image of $x^2+1$ has roots when you consider it as an element of $\mathbb{C}[x]$, but no roots when you consider it as an element of $\mathbb{Z}[x]$. No, you cannot say that a polynomial in $\mathbb{F}_p[x]$ has roots in $\mathbb{C}$; that makes no sense precisely because $\mathbb{C}$ does not contain $\mathbb{F}_p$. – Arturo Magidin Apr 26 '11 at 4:35
@badatmath: But the reason $x^2+1$ has roots in $\mathbb{F}_p$ when $p\equiv 1 \pmod{4}$ is that in those situations, $-1$ is a square modulo $p$. For example, in $\mathbb{F}_5$, but $2\bmod 5$ and $3\bmod 5$ are roots of (the image of) $x^2+1$. – Arturo Magidin Apr 26 '11 at 4:36
Oh, okay. So you can't say that because the inclusion map does not exist. Thanks. – badatmath Apr 26 '11 at 5:18

Last question first, $2x-1$ certainly doesn't have the same roots in $\bf Z$ as in $\bf Q$. I'd say $x-2$ has the same root in $\bf Z$ as in $\bf Q$, namely, $2$, but I can imagine some situation in which one might want to distinguish between $2$ as an integer and $2$ as a rational.

Does $x-7$ have the same root in $\bf Z$ as in ${\bf F}_5$? I think it would be an abuse of notation to say yes. But abuses of notation can be very useful, so I wouldn't rule it out; I'd just make absolutely sure to put all my cards on the table first, that is, to say something like we identify elements of $\bf Z$ with their images in ${\bf F}_5$'' first.

-

No. In fact, this failure can be rather extreme, as for polynomial rings over finite fields there are nonzero polynomials with integer coefficients that vanish at every point in the field. Easy examples are provided by encoding boolean contradictions as polynomials in $\mathbb{F}_2[X]$, such as $(x \text{ and } x)\text{ xor } x$ which is represented as $x^2 + x$ or $((x \text{ and } x)\text{ and } x) \text{ xor } x$ which is represented as $x^3 + x$. You can also get such polynomials in $\mathbb{F}_p[X]$ by taking the product $(x - (p - 1))(x - (p - 2))\cdots (x - 1)x$.

-

Echoing Arturo, since there's a surjection $\phi: \mathbb{Z}[x] \to \mathbb{F}_p[x]$, if $a$ is a root of $f$ in $\mathbb{Z}[x]$, then $\phi(a)$ is a root of $f$ in $\mathbb{F}_p[x]$. So a root in $\mathbb{Z}[x]$ translates into a root in $\mathbb{F}_p$, but they can overlap. For example, $x^2 - 1 = (x+1)(x-1)$ has two distinct roots $1,-1$ in $\mathbb{Z}[x]$ but one repeated root $1$ in $\mathbb{F}_2[x]$.
In the same line as Alex's comment, you have to be a little careful. If $p$ divides every coefficient of $f$, then $f \equiv 0$ in $\mathbb{F}_p[x]$.
In addition, some irreducible elements in $\mathbb{Z}[x]$ do factor in $\mathbb{F}_p[x]$. See Arturo's answer.
In general, it's easier to factor in $\mathbb{F}_p[x]$ because there are fewer elements to check divisibility by. And that can help determine factorization in $\mathbb{Z}[x]$. A theorem states that if the leading coefficient of $f$ is not divisible by $p$, and if $f$ is irreducible in $\mathbb{F}_p$, then $f$ is irreducible in $\mathbb{Z}$ (Artin 2nd Edition 12.4.3). The converse does not hold for the same reasons as discussed in the previous paragraph.
Factorization in $\mathbb{Z}[x]$ and $\mathbb{Q}[x]$ is equivalent up to constant multiples, but linear factors are always roots in $\mathbb{Q}[x]$, while they aren't necessary so in $\mathbb{Z}[x]$, as Gerry stated. Roots in $\mathbb{Z}[x]$ will be roots in $\mathbb{Q}[x]$, but not necessarily the other way around.