# Roots of polynomials over GF(p)

by joeblow
Tags: polynomials, roots
 P: 71 If F is a field of characteristic p, with prime subfield K = GF(p) and u in F is a root of f(x) (over K), then $u^p$ is a root of f(x). Now, I know that $x^p \equiv x (\text{mod } p)$, so isn't it immediately true that $f(x^p)=f(x)$ (over K)? So, $0=f(u)=f(u^p)$. I only ask because this type of problem (as I understand it) is much more elementary than the material that the text is covering. In the section from which this problem comes, the main results are (1) that if F = GF(q), then the irreducible factors of $x^{q^{m}}-x$ over F are precisely the irreducible polynomials over F of degree dividing m, (2) the Mobius inversion formula, and (3) a formula for finding the number of monic irreducible polynomials of degree m over GF(q). Please tell me if there is some critical misunderstanding that I am having.
 P: 71 The result that $(a+b)^p=a^p+b^p$ (which is all that is needed) was demonstrated (via exercise) much earlier in the chapter, though. Something is strange about the placement of this problem.
 Emeritus Sci Advisor PF Gold P: 16,091 Roots of polynomials over GF(p) It is true that, for every element $a$ of GF(p), we have $a^p = a$. As a consequence, it's also true that, for every integer $n$, we have $n^p \equiv n \pmod p$. Also as a consequence, for every polynomial with coefficients from GF(p) and element $a$ of GF(p), we have $f(a) = f(a^p)$. Similarly, for every polynomial with integer coefficients and any integer $n$, we have $f(n^p) \equiv f(n) \pmod p$. (Yes, I mean = where I've written =, and $\equiv$ where I've written $\equiv$) If $x$ is an indeterminate over GF(p), then it's not true that $x^p = x$. Consequently, if $t$ is an indeterminate over Z, it's not true that $t^p \equiv t \pmod p$. (While $x$ and $x^p$ both determine the same function on GF(p), they are different polynomials. And, e.g., they give different functions on GF($p^2$)) If $u \notin \text{GF}(p)$, then we have no reason to expect $u^p = u$. If $u$ is not an integer, we have no reason to expect $u^p \equiv p \pmod p$ (if that equation even makes sense). For a finite field $\text{GF}(p^e)$, the operation $a \mapsto a^p$ is actually generalization of the idea of conjugation. For the special case of $e = 2$, you even have that $(a^p)^p = a$. (for larger $e$, you have to iterate $e$ times rather than just twice)