Show that $f(x)=x^2+x+4$ is irreducible over $\mathbb{Z}_{11}$ I know this can be done by evaluating $f$ at the points $0,1,...10$ to check if $f$ has a linear factor.
Is there any other shorter way?
 A: We start with $$x^2+x+4=0$$ multiplying with $4$ we get $$4x^2+4x+16=0$$ This can be written as $$(2x+1)^2+15=0$$ modulo $11$ this is equivalent to $$(2x+1)^2-7=0$$
So we have to solve $$(2x+1)^2\equiv 7\mod 11$$
Using the quadratic reciprocity law we can calculate the legendre symbol
$$(\frac{7}{11})=-(\frac{11}{7})=-(\frac{4}{7})=-1$$
Hence $u^2\equiv 7\mod 11$ is not solveable because $7$ is not a quadratic residue modulo $11$. Since $x^2+x+4$ has no root in $\mathbb Z_{11}$, it follows that $x^2+x+4$ is irreducible in $\mathbb Z_{11}$
A: In ${\mathbb Z}_{11}$, the discriminant of $x^2 + x + 4$ is $1 - 4 \cdot 4 = 7$, so this polynomial has a root in ${\mathbb Z}_{11}$ if and only if $7$ is a square modulo $11$. Using the law of quadratic reciprocity, $$\left(\frac{7}{11}\right) = -\left(\frac{11}{7}\right) = -\left(\frac{4}{7}\right) = -1,$$ so $7$ is not a square modulo $11$.
(This is essentially Peter's method, just jumping directly to the fact that you have to check whether or not $7$ is a quadratic residue modulo $11$.)
A: The discriminant of the quadratic form $u^2 + uv + 4 v^2$ is $-15.$ 
$$ (-15|11) = (-4|11) = (-1|11) (4|11) = (-1|11)=-1,  $$
the last part because $11 \equiv 3 \pmod 4.$
Therefore, if
$$ u^2 + uv + 4 v^2 \equiv 0 \pmod {11}, $$ it follows that both $u,v$ are divisible by $11.$ General theorem with proof at Prime divisors of $k^2+(k+1)^2$
So, with integer $x,$ $x^2 + x + 4$ is the same as $x^2 + xy + 4 y^2$ restricted to $y=1;$ that is, this $y$ is not divisible by $11.$ So $x^2 + x + 4$ cannot be divisible by $11$  
I like this way of writing things, in quadratic forms this behavior is called "anisotropic." My experience is that existence of a solution that, however, violates some condition, is easier for the student to deal with than "infinite descent" arguments. All is the same, just a matter of emphasis.
Sigh. Same thing: $x^2 + 1$ is not divisible by any prime $q \equiv 3 \pmod 4.$ The discriminant of $u^2 + v^2$  is $-4.$ For such $q,$ if $q | (u^2 + v^2)$ then both $q|u$ and $q | v.$ However, it is not possible to have $q | 1,$ so $q$ cannot divide $x^2 + 1$ either.
