How can I determine if a polynomial is factorizable in $Z_p[x]$? First of all, sorry for my bad English.

I am looking for a general method to know for which primes $p$ a specific polynomial factorize in $Z_p[x]$.

For example my teacher considers $(x^3-1)=(x-1)(x^2+x+1)$ and wants to factorize $x^2+x+1$. He considers $p=5$ and replaces all elements of $Z_5$ instead of $x$; $x^2+x+1$ is never zero, so does not factorize. For $p=13$ he obtains zero, so in $Z_{13}$ the polynomial factorizes. Then he proves that it is possible to factorize $x^2+x+1$ in $Z_p$ if and only if $p \equiv 1 \pmod{3}$. In the first direction of the proof (polynomial factorize in $Z_p$ implies $p \equiv 1 \pmod{3}$) he takes a $z$ in $Z_p$ that is a zero for $x^2+x+1$ and implies that $z^3 \equiv 1 \pmod{p}$. Why?
If I have a different polynomial in $Z_p$ there is a general method to determine the equivalence class of $p$ like in the example? It maybe involves the polynomial's degree?
Thanks for your help!
 A: In general, the Berlekamp algorithm can give us a factorization of a given polynomial in $\mathbb{F}_p[x]$ for a prime $p$. If you want results for all $p$, there is no easy general congruence condition in general. For cyclotomic polynomials however see the discussion in
 this question. Sometimes we obtain easy conditions, e.g., the polynomial $x^4+1$ is for no prime $p$ irreducible over $\mathbb{F}_p$, see here.
A: There is a general method for prime $p$ and
$$ a x^2 + bx + c $$
given by repeating the derivation of the Quadratic Formula. For primes $p \neq 2$ and $$ b^2 - 4 a c \neq 0 \pmod p, $$
we can factor when there is an ordinary integer $t$ such that
$$ t^2 \equiv b^2 - 4 a c \pmod p.  $$ Notice that, if $p | a,$ we may then take $t=b,$ but the thing is no longer quadratic anyway.
I would guess you will learn the Legendre symbol and quadratic reciprocity next.
After quadratics, it gets very hard, even for cubic polynomials. Unless you want a computer to do the factoring for you, which will work for one prime at a time, you may be dealing with class field theory, advanced material. For example
$$  x^3 - x + 1 $$
is irreducible for primes 
$$ p = 2 u^2 + uv + 3 v^2,  $$ for some integers $u,v.$ I don't recall what happens when $p=23.$
The cubic factors into three distinct linear factors for
$$ p =  u^2 + uv + 6 v^2.  $$ Then $  x^3 - x + 1 $ factors as a linear times a quadratic when Legendre symbol $(-23|p) = -1.$
There are just a few examples of cubics where one may use reciprocity laws without resorting to class field theory. Ireland and Rosen do this one, proved by Gauss: 
$$  x^3 - 2 $$
is irreducible for primes 
$$ p = 4 u^2 + 2uv + 7 v^2,  $$ for some integers $u,v.$ 
The cubic factors into three distinct linear factors for
$$ p =  u^2  + 27 v^2.  $$ Then $  x^3 - 2 $ factors as a linear times a quadratic when Legendre symbol $(-3|p) = -1.$
Jacobi proved: 
$$  x^3 - 3 $$
is irreducible for primes 
$$ p = 7 u^2 + 3uv + 9 v^2,  $$ for some integers $u,v.$ 
The cubic factors into three distinct linear factors for
$$ p =  u^2  + uv + 61 v^2.  $$ Then $  x^3 - 3 $ factors as a linear times a quadratic when Legendre symbol $(-3|p) = -1.$
