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?
Best Answer
(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).