# 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 -

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

-
To answer your first question, you can use either long division or trial and error. As for the second question, there isn't a more efficient method I am aware of right now, but that isn't to say there isn't a better way. –  Clayton Apr 17 '13 at 21:06
The problem is that long devision over finite fields is just not "working right" for some reason . An example could be great –  itamar Apr 17 '13 at 21:11
@itamar, perhaps you're perfomring the long division without making arithmetic modulo 5 (or 7)? Because it works just fine over any field, whether finite or not. –  DonAntonio Apr 17 '13 at 21:42
The usual rules of degree work for polynomials over a finite field, so try multiplying out and solving solving $x^{2}-2 = (x-3)(x-b)$ mod $7$ for $b$. –  tharris Apr 17 '13 at 21:43

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]$.
$3^2 = 9 \equiv 2 \bmod 7$. –  Dilip Sarwate Apr 18 '13 at 9:41
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$.