Roots of polynomials over GF(p)


by joeblow
Tags: polynomials, roots
joeblow
joeblow is offline
#1
Mar16-12, 10:27 AM
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 [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.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
Norwegian
Norwegian is offline
#2
Mar16-12, 01:03 PM
P: 144
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.
joeblow
joeblow is offline
#3
Mar16-12, 09:29 PM
P: 71
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.

Hurkyl
Hurkyl is offline
#4
Mar17-12, 12:34 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101

Roots of polynomials over GF(p)


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)


Register to reply

Related Discussions
Roots of polynomials Calculus & Beyond Homework 2
Proof of roots of polynomials General Math 4
Roots of polynomials... Precalculus Mathematics Homework 7
multiple roots of polynomials Calculus & Beyond Homework 5
Roots of Complex Polynomials Calculus 1