# Roots of polynomials over GF(p)

1. Mar 16, 2012

### joeblow

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.

2. Mar 16, 2012

### Norwegian

In general, we dont have f(u)=f(up) in your field F, but only for u in K, and you also need to use that (a+b)p=ap+bp for any a,b in F. Then it should be easy and fun to write out 0=f(u)p and see where that leads.

3. Mar 16, 2012

### joeblow

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.

4. Mar 17, 2012

### Hurkyl

Staff Emeritus
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)