Roots of polynomials over GF(p)

  1. Mar 16, 2012 #1
    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 [itex]u^p[/itex] is a root of f(x).

    Now, I know that [itex] x^p \equiv x (\text{mod } p)[/itex], so isn't it immediately true that [itex] f(x^p)=f(x) [/itex] (over K)? So, [itex] 0=f(u)=f(u^p) [/itex].

    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 [itex]x^{q^{m}}-x[/itex] 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. jcsd
  3. Mar 16, 2012 #2
    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.
  4. Mar 16, 2012 #3
    The result that [itex](a+b)^p=a^p+b^p[/itex] (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.
  5. Mar 17, 2012 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It is true that, for every element [itex]a[/itex] of GF(p), we have [itex]a^p = a[/itex]. As a consequence, it's also true that, for every integer [itex]n[/itex], we have [itex]n^p \equiv n \pmod p[/itex]. Also as a consequence, for every polynomial with coefficients from GF(p) and element [itex]a[/itex] of GF(p), we have [itex]f(a) = f(a^p)[/itex]. Similarly, for every polynomial with integer coefficients and any integer [itex]n[/itex], we have [itex]f(n^p) \equiv f(n) \pmod p[/itex].

    (Yes, I mean = where I've written =, and [itex]\equiv[/itex] where I've written [itex]\equiv[/itex])

    If [itex]x[/itex] is an indeterminate over GF(p), then it's not true that [itex]x^p = x[/itex]. Consequently, if [itex]t[/itex] is an indeterminate over Z, it's not true that [itex]t^p \equiv t \pmod p[/itex].

    (While [itex]x[/itex] and [itex]x^p[/itex] both determine the same function on GF(p), they are different polynomials. And, e.g., they give different functions on GF([itex]p^2[/itex]))

    If [itex]u \notin \text{GF}(p)[/itex], then we have no reason to expect [itex]u^p = u[/itex]. If [itex]u[/itex] is not an integer, we have no reason to expect [itex]u^p \equiv p \pmod p[/itex] (if that equation even makes sense).

    For a finite field [itex]\text{GF}(p^e)[/itex], the operation [itex]a \mapsto a^p[/itex] is actually generalization of the idea of conjugation. For the special case of [itex]e = 2[/itex], you even have that [itex](a^p)^p = a[/itex]. (for larger [itex]e[/itex], you have to iterate [itex]e[/itex] times rather than just twice)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Roots of polynomials over GF(p)
  1. Roots of polynomial (Replies: 3)