$x^2+3x+3$ is irreducible in $\mathbb{F}_{25}[x]$

Question

Give an example of an irreducible non-linear polynomial in $\mathbb{F}_{25}[x]$.

I know that $x^2+3x+3$ is irreducible in $\mathbb{F}_{25}[x]$ but I know no shorter proof then the exhaustive search (since $\mathbb{F}_{25}[x]$ is not a factorial ring we cannot use Eisenstein's criterion).

Can you please help me to find a more elegant idea?

Answer 1

The quadratic formula works very well in any non-characteristic-$2$ field. So the roots of your $x^2+3x+3$ are $$ \frac{-3\pm \sqrt{3^2 - 4\cdot 1\cdot 3}}{2\cdot 1} = 1\pm3\sqrt2 $$ Since $\Bbb F_{25}$ is a quadratic extension of $\Bbb F_5$, it contains all the square roots of any element in $\Bbb F_5$. So $\sqrt 2$ actually exists in $\Bbb F_{25}$, and your polynomial has roots. In fact, we get that any quadratic polynomial over $\Bbb F_5$ has roots in $\Bbb F_{25}$. So in order to find irreducible quadratics, you need to use at least one of the twenty non-$\Bbb F_5$ elements of $\Bbb F_{25}$.

For instance, we could take $x^2 + \sqrt2$. There is no square root to $\sqrt2$ in $\Bbb F_{25}$ (proof below), so this is irreducible.

All elements in $\Bbb F_{25}$ may be written in a unique way as $a + b\sqrt2$, where $a, b\in \Bbb F_5$. If $\sqrt2$ has a square root in $\Bbb F_{25}$, then we have a solution to $$ (a + b\sqrt2)^2 = \sqrt2\\ a^2 + 2b^2 + 2ab\sqrt2 = \sqrt2\\ a^2 + 2b^2 = 0\quad\land\quad 2ab = 1 $$ The only solution in $\Bbb F_5$ to $a^2 + 2b^2 = 0$ is $a = b = 0$, but that doesn't solve $2ab = 1$, so $\sqrt{\sqrt2}$ doesn't exist in $\Bbb F_{25}$.

Answer 2

Your suggested polynomial $f$ is irreducible in $\Bbb F_5[X]$. Therefore $\Bbb F_5[X]/(f)$ is a quadratic extension of $\Bbb F_5$, hence is already $\Bbb F_{25}$, and by construction $f$ has a root there.

Answer 3

The polynomial you're trying with is reducible, as others have already pointed out. Degree two polynomials with coefficients in $\mathbb{F}_5$ don't work: they're all reducible in $\mathbb{F}_{25}[x]$.

What about a cubic polynomial? It's easy to test whether it's irreducible over $\mathbb{F}_5[x]$: it just needs to have no root. So let' try the simplest one $$ f(x)=x^3+x+1 $$ Then $f(0)=1$, $f(1)=3$, $f(2)=1$, $f(3)=1$, $f(4)=4$.

Can you see why this polynomial is also irreducible in $\mathbb{F}_{25}$?