# 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?

• Notice that $x^2+x+4\equiv (x+6)^2+1\pmod{11}.$ And I think your proof for $(i)$ works just fine. – awllower Apr 28 '15 at 10:22

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.

(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).

• No need to invert $2$ since one can choose an even rep for the coeff of $\,x^1,\,$ see my answer. – Bill Dubuque Apr 28 '15 at 14:52

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.

• @St Vincent: I don't agree with the replacement of equality with congruence symbol: my explanation happen in the set $\mathbf Z/11\mathbf Z$, not in $\mathbf Z$. That's why I can write $2^{-1}=6$. Congruence is for integers, not residue classes. – Bernard Apr 28 '15 at 13:05