Checking irreducibility of a polynomial over a finite field

Question

A part of a coding theory course I am doing includes some questions on irreducible polynomials.

I have a question with solution but am worried I have interpreted it incorrectly.

So for $\mathbb F_5$ and polynomials $X^2+2$ and $X^2+X+2$, I want to find whether each is irreducible or not.

The field $\mathbb F_5 = \{0,1,-1,2,-2:5=0\}$.

And I think this is what is confusing me, as I would have used field F_5 = {0,1,2,3,4:5=0}$ and then the question would have not been a problem. However,

it says $f_1(x)=X^2+2$ so $f_1(0)=2$, $f_1(1)=-2$ and $f_1(-1)=-2$.

Then is says $f_1(-2)=f_1(2)=-1$ but I would have said $f_1(-2)=f_1(2)=X^2+2=4+2=6mod5=1$ this is the only one I am confused about

Then for the second polynomial it says $f_2(1)=-1$ and $f_2(-1)=1$.

I will put the rest of results in here so the full answer can be seen:

$f_2(0)=2$(I understood this one, obviously), $f_2(2)=-2$ and $=f_2(-2)$

Thanks!

Answer 1

You can think of $\mathbb{F}_5$ as $\{0,1,2,3,4\}$ or you can think of it as $\{-2,-1,0,1,2\}$. They are both simpler ways of writing the same thing:

$$\mathbb{F}_5 = \{\left(\begin{matrix}\vdots\\-7\\-2\\3\\8\\\vdots\end{matrix}\right),\left(\begin{matrix}\vdots\\-6\\-1\\4\\9\\\vdots\end{matrix}\right),\left(\begin{matrix}\vdots\\-5\\0\\5\\10\\\vdots\end{matrix}\right),\left(\begin{matrix}\vdots\\-4\\1\\6\\11\\\vdots\end{matrix}\right),\left(\begin{matrix}\vdots\\-3\\2\\7\\12\\\vdots\end{matrix}\right)\}$$

I.e. when working in $\mathbb{F}_5[x]$, the following are all equivalent: $x^2+1\equiv x^2-4\equiv -4x^2+1\equiv 11x^2+6$ because $11\equiv 6\equiv 1\equiv -4\mod{5}$.

As for the question of if $x^2+2$ is irreducible, it may help to view it instead as $x^2+2\equiv x^2-3$. If it were in fact reducible, then by the fact that it is of order two there would need to be a linear factor that divides it, so that $x^2-3 = (x-a)(x-b)$. But, that would imply that for $x=a$ you would have $(a-a)(a-b)=a^2-3=0$ which in turn implies that $a^2=3$. We check to see if $3$ is a square in $\mathbb{F}_5$. By guess and check, we see $0^2=0\neq 3,1^2 = 1\neq 3, 2^2=4\neq 3, 3^2 = 9\equiv 4\neq 3, 4^2 = 16\equiv 1\neq 3$, so $3$ is not a square and therefore the first polynomial is in fact irreducible.

(this is perhaps the reason they recommended using $-2,-1,0,1,2$... the math is easier. Note we would have calculated $(-2)^2=4$ instead of $3^2=9\equiv 4$ and $(-1)^2=1$ instead of $4^2=16\equiv 1$, saving some thought)

---

Although your second polynomial is illegible, given your work, we can assume you mean the second polynomial is $x^2+x+2$.

We can go through the same process. First we argue that if there was a way to reduce the polynomial, since it is degree two it must break into two linear factors, i.e. $x^2+x+2=(x-a)(x-b)$.

Noting again that if $x=a$ that would imply that $a^2+a+2=(a-a)(a-b)=0$, we ask ourselves if any such $a$ exists.

You should have proceeded to calculate $f_2(-2)$ to see if it equaled zero. $(-2)^2+(-2)+2 = 4 - 2 + 2 = 4\equiv -1$.

Answer 2

For any polynomial $p$ over $\Bbb R$, $\color{blue}{a} \in \Bbb R$ is a root of $p$ (that is, $p(\color{blue}{a}) = 0$) iff $X - \color{blue}{a}$ is a factor of $p(X)$, that is, iff there is a polynomial $q$ such that $$p(X) = (X - \color{blue}{a}) q(X).$$

The statement is true if we replace $\Bbb R$ with $\Bbb F_5$. Now, over the latter field we have the advantage: It has only finitely many elements, so to check whether a polynomial $p \in \Bbb F_5[X]$ has any linear factors, it is enough to check whether any of $p(0), \ldots, p(4)$ is zero (as elements of $\Bbb F_5$!).

Now, a quadratic polynomial (over any field) either is irreducible or not. In the latter case, it factors as a product of two linear factors. So, by the fact above, to check whether a quadratic polynomial $p \in \Bbb F_5[X]$ is irreducible it's enough again to check whether $$p(0), \ldots, p(4)$$ is zero.

In our case, checking the first polynomial, $f_1(X) = X^2 + 2$, gives \begin{align} f_1(0) &= (0)^2 + 2 = 0 + 2 = 2\\ f_1(1) &= (1)^2 + 2 = 1 + 2 = 3\\ f_1(2) &= (2)^2 + 2 = 4 + 2 = 1\\ f_1(3) &= (3)^2 + 2 = 4 + 2 = 1\\ f_1(4) &= (4)^2 + 2 = 1 + 2 = 3 . \end{align} Note that we've written $f_1(1) = 3$ just as you claimed, and not $f_1(1) = -2$ as in your notes/solution; this is okay, as $3 = -2$ in $\Bbb F_5$ (since $5 = 0$ in this field, we have $-2 = -2 + 0 = -2 + 5 = 3$). Now, none of these values are $0$, so we can conclude that $f_1 \in \Bbb F_5[X]$ is irreducible.

Note that the same argument applies to cubic polynomials but not polynomials of higher degree, as polynomials of degree $\geq 4$ can be reducible but have no linear factors. Over $\Bbb F_5$, for example, $(X^2 + 2) (X^2 + X + 1)$ is reducible, but we showed above that its quadratic factors are irreducible, so it has no linear factors.