# Irreducible polynomials on $\mathbb Z_2$ and $\mathbb Z_k$

I had to solve many exercises to take my algebra exam lately and lots of them are on polynomials, whereas I am asked to look for roots and verify if the given polynomials are reducible in a specific $F[x]$ field or not.

I have noticed something while doing these exercises and I don't really know if my intuition is supported by some actual theorem (and that is why I am asking for your kind help), so I am wondering:

say $p(x)$ is a polynomial over $\mathbb Z_2$, is it possible that if $p(x)$ is irreducible in $\mathbb Z_2$ then it is irreducible in every $\mathbb Z_n \text { } (\forall n > 2)$?

and generally speaking is is true that if a polynomial $p(x)$ is irreducible in a certain $\mathbb Z_k \Rightarrow p(x)$ is irreducible in $\mathbb Z_j$ $(\forall j > k)$?

-
If $p$ has coefficients in $\Bbb Z/(2)$ then how does it also have coefficients in $\Bbb Z/(n)$ for every $n$? I think you want $p(x)\in\Bbb Z[x]$ and then consider irreducibility of $p(x)$'s image under the quotient maps $\Bbb Z[x]\to \Bbb Z/(n)[x]$. –  anon Sep 3 '12 at 18:07
This is very false. I will give just one counterexample: $x^3 + x + 1$ is irreducible mod 2 but is reducible mod 3, 11, 13, 17, 23,.... In fact, there is a theorem that if a monic polynomial with integral coefficients is irreducible mod $p$ for all but finitely many $p$ then it must be a linear polynomial. –  KCd Sep 3 '12 at 18:11

The coefficients of $p(x)\in\mathbb Z_2[x]$ are elements of $\mathbb Z_2$, that is either $2\mathbb Z$ or $1+2\mathbb Z$. We cannot consistently make coefficients in $\mathbb Z_n$ from that. For example, $x^2 \in \mathbb Z_2[x]$ might be lifted to $3x^2+2\in \mathbb Z_5[x]$, one need not take $x^2\in \mathbb Z_5[x]$.
However, to make sense of the question: Let $p(x)\in \mathbb Z[x]$ be a polynomial whose coefficients are all in $\{0, 1\}$. Then we can consider the reduced polynomials $p_n(x)\in\mathbb Z_n[x]$ for all $n\ge 2$. Question: If $p_2(x)$ is irreducible, does that imply that all $p_n(x)$ are irreducible? The answer is "no", as can be seen from this counterexample: For $p(x):=x^2+x+1\in \mathbb Z[x]$ its reduction $p_2(x)$ is irreducible because any nontrivial factor must be linear, i.e. lead to a root in $\mathbb Z_2$. But $p_2(0)=p_2(1)=1$. On the other hand, $p_3(x) = (x-1)^2$ is reducible.