Roots of polynomials over finite fields

Question

I've been trying to find the decomposition of $x^2-2$ to irreducible polynomials over $\mathbf{F}_5$ and $\mathbf{F}_7$. I know that for some $a$ in $\mathbf{F}_5$ (for example), $x-a$ divides $x^2-2$ iff $f(a) = 0$, i.e $a$ is a root of $x^2-2$. Over the field $\mathbf{F}_7$, I've found (by trail and error) that one irreducible polynomial is $x-3$. I've now got two questions -

1. How can I find the other irreducible polynomial?
2. Is there any more efficient method to find roots than trial and error?

Thanks in advance

Answer 1

There are many ways of looking at this, but you’re just being asked to find a number that squares to $2$, modulo $5$ in the first case, modulo $7$ in the second. You can check that no matter what you square modulo $5$, the results are always $0$, $1$, $4$, so that $2$ has no square root here, and your polynomial is irreducible. Modulo $7$, it’s $0$, $1$, $2$ (because $3^2\equiv2\pmod7\>$) and $4$. Since you’ve found one square root of $2$ modulo $7$, the other is, of course, $-3\equiv4\pmod7$. Thus $x^2-2=(x-3)(x-4)$ over $\mathbb F_7$.

Answer 2

In a field of characteristic other than $2$, the usual quadratic formula $$\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$ provides the roots of the quadratic polynomial $ax^2+bx+c$. So the roots of $x^2-2 = 2\left(\frac{1}{2}x^2-1\right)$ are $$\frac{-0\pm\sqrt{0^2-4\times\frac{1}{2}(-1)}}{2\times \frac{1}{2}} = \pm \sqrt{2}.$$ In $\mathbb F_5$, $2$ is not a quadratic residue and so $\sqrt{2}$ is not an element of $\mathbb F_5$, that is, $x^2-2$ is irreducible over $\mathbb F_5$. It does factor into two polynomials of degree $1$ in $\mathbb F_{5^2}[x]$. On the other hand, $\sqrt{2} = 3$ in $\mathbb F_7$ and so $x^2-2$ factors into two polynomials of degree $1$ in $\mathbb F_7[x]$.