Roots of polynomials over finite fields 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 - 


*

*How can I find the other irreducible polynomial? 

*Is there any more efficient method to find roots than trial and error?


Thanks in advance 
 A: 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]$.
A: 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$.
