# Proving a polynomial is irreducible over a finite field

Question: $\mathbb{F}_5=\{0,1,2,3,4,5\}$ be the field with $5$ elements, let $\mathbb{F}_5[X]$ be the polynomial ring over $\mathbb{F}_5$. Let $m(X) = X^2+X+1$. Prove that $m(X)$ is irreducible over $\mathbb{F}_5$.

Proof.

Suppose $m(X)$ is reducible then there exist $r(X),q(X)$ where $\deg r(X)=\deg q(X)= 1$

So by the quadratic formula we have

$$m(X)= \left(X-\left(\frac{-1+3i}{2}\right)\right)\left(X-\left(\frac{-1-3i}{2}\right)\right)$$

However $$\frac{-1+3i}{2},\frac{-1-3i}{2}\notin \mathbb{F}_5.$$

Therefore $m(X)$ is irreducible.

Would this be correct?

• Notice that $\Bbb F_5=\{0,1,2,3,4\}$ – Masacroso Oct 7 '16 at 10:52
• You can show (by simply plugging in all values) that $m(X)$ has no roots over $\mathbb{F}_5$. – Janik Oct 7 '16 at 10:59
• Not sure how you applied the quadratic formula. $i$, as in $\sqrt {-1}$ is an element of $\mathbb F_{\,5}$ as $2^2=-1\pmod 5$. But you should have had $\sqrt {-3}$ and $-3$ is not a square $\pmod 5$. – lulu Oct 7 '16 at 11:03
• I'm sorry, I don't quite understand how modulus is involved? Isn't this a polynomial ring? – aoshdosi Oct 7 '16 at 11:12
• Working in $\mathbb F_{\,5}$ is the same as working in the integers $\pmod 5$. – lulu Oct 7 '16 at 11:20

A quadratic polynomial with integer coefficients is irreducible over a finite field $\mathbb{F}_p$ iff it has no root in $\mathbb{F}_p$, i.e. iff its discriminant is not a square in $\mathbb{F}_p$. Since the discriminant of $x^2+x+1$ is $-3$ and $-3\equiv 2$ is not a square $\!\!\pmod{5}$ (the set of squares is made by the residue classes $0,1,4$ only), it follows that $x^2+x+1$ is irreducible over $\mathbb{F}_5$.
Notice that the complex roots of $x^2+x+1=\Phi_3(x)$ are $\frac{1\pm\sqrt{-3}}{2}$ and not what you wrote.
• @aoshdosi: $\mathbb{F}_5$ is the finite field with $5$ elements. The prime $p$ defining $\mathbb{F}_p$ has to play some role! In our case $p=5$. The squares $\pmod{5}$ are $0,1,4$; the discriminant of our polynomial is not $0,1$ or $4\pmod{5}$. – Jack D'Aurizio Oct 7 '16 at 11:16