<s>[INST] Show that $x^2+x+4$ is irreducible over $\mathbb Z_{11}$. 
Show that $x^2+x+4$ is irreducible over $\mathbb Z_{11}$. 

The problem can be solved by putting every element from $\mathbb{Z}_{11}$ and checking if there is any root.
$0^2 + 0 + 4 = 4 \\
1^2 + 1 + 4 = 6 \\
2^2 + 2 + 4 = 10 \\
3^2 + 3 + 4 = 5 \\
4^2 + 4 + 4 = 2 \\
5^2 + 5 + 4 = 1 \\
6^2 + 6 + 4 = 2 \\
7^2 + 7 + 4 = 5 \\
8^2 + 8 + 4 = 10 \\
9^2 + 9 + 4 = 6 \\
10^2 + 10 + 4 = 4 $ 
But this process is very long one. I am seeking a short method by which I can solve such problem. 
Now suppose that it is reducible, then the factors should be linear. So how can we solve the problem based on this kind of observation? Any help will be great. Thanks.
 [/INST] ${\rm mod}\ 11\!:\,\ 0\equiv x^2\!+\!x\!+\!4\equiv x^2\!+\!12x\!+\!4\equiv (x\!+\!6)^2\!+1\,\Rightarrow\,(x\!+\!6)^2\equiv -1.$
But $\,-1\,$ is not a square, else by little Fermat:  $\left[ a^2\equiv -1\right]^5\Rightarrow\, 1\equiv -1.$
Remark $ $ We implicitly applied Euler's Criterion to show $-1$ is not a square $\!\bmod 11.\,$  More generally we can use Legendre or Jacobi symbols or the generalized Euler Criterion.
</s>