Irreducibility of polynomials over finite field of integers $\bmod 11$. 
Theorem (Fermat's little Theorem). If $p$ is a prime and $a \in \mathbb{Z}$ with $a \nmid p$ then $a^{p-1} \equiv 1 \mod p.$

Let $\mathbb{Z}/p\mathbb{Z}$ denote the multiplicative group of integers modulo $p.$ Let $k$ be the order of $a.$ Then $a^k \equiv 1 \mod p.$ By Lagrange's theorem, the order of the element $k$ divides the order of the group $|(\mathbb{Z}/p\mathbb{Z})^{\times}| = p-1$ (since the order of $a$ is equal to the subgroup generated by $a$) so $p -1 = kq$ for some $q \in \mathbb{Z}.$ Therefore $a^{p-1} \equiv a^{kq} \equiv (a^k)^q \equiv 1^q \equiv 1. \hspace{1mm} \Box $

(i) Prove that $x^2+1$ is irreducible over the integers $\operatorname{mod} 11$.

Since the degree of $x^2+1$ is equal to $2,$ it follows that $x^2+1$ is reducible $\Longleftrightarrow x^2+1$ has a root in the finite field $\mathbb{Z}/11\mathbb{Z}.$ Suppose to the contrary that a root $a \in \mathbb{Z}/11\mathbb{Z}$ exists. Then $a^2 +1 \equiv 0 \mod 11 \Longrightarrow a^2 \equiv - 1 \equiv 10 \mod 11.$ By considering the multiplicative group $(\mathbb{Z}/11\mathbb{Z})^{\times}$ and applying the above theorem, $a^{11-1} \equiv a^{10} \equiv 1 \mod 11$ but since $a^{10} \equiv (a^2)^5 \equiv (-1)^5  \equiv -1 \mod 11,$ we have reached a contradiction.

(ii) Prove that $x^2+x+4$ is irreducible over the integer $\operatorname{mod} 11.$

(Show that none of the $11$ elements in the finite field $\mathbb{Z}/11\mathbb{Z}$ are congruent to $0 \mod 11.$)
First question: Does the proof for $(i)$ work?
Second: What's a good trick to prove $(ii)$ without plugging in elements from the field explictly?
 A: (i) works fine.
For (ii), complete the square in $\mathbf Z/11\mathbf Z$ (note $2^{-1}=6 =-5)$. You'll be brought back to case (i).
A: Your proof of (i) is sufficient. 
For (2), you of course could check the $11-1 =10$ nontrivial elements of the field explicitly. Alternatively, the proof of the quadratic formula works over any field such that $2\neq 0$. So in particular, it works over $\mathbb{Z}/11\mathbb{Z}$.
Thus, check to see it is irreducible, it suffices (since it is degree 2) to show it has no roots using the quadratic formula. This is just checking whehter the discriminant $b^2-4ac$ is a square in this field or not.
A: Yes, the proof of $(i)$ is correct (it is essentially half  of the proof of Euler's Criterion).
For $(ii)$ note $\ x^2\!+\!x\!+\!4 \equiv x^2\!-\!\color{#c00}{10}x\!+\!4 \equiv (x^2\!-\!5)^2\!+\!1 \equiv X^2\!+\!1\,$ so $(i)$ applies. 
Remark $\ $ We chose an even rep $\,\color{#c00}{-10\equiv 1}\,$ for the coefficient $\,b\,$ of $\,x^1\,$  (to complete the square). This trick works for any odd modulus since one of $\,b\equiv b\pm n\,$ is even, by $\,n\,$ odd.
