Which field will contain all the roots of a polynomial over $GF(p)$

Question

Given a a polynomial with coefficients in $GF(p)$ and degree $d$, will that polynomial always have $d$ roots in $GF(p^d)$?

The text I am reading seems to be implying that this is true but I can't see why.

Answer 1

In my opinion the theory of finite fields is much clearer if one works in the algebraic closure $\overline{\mathbb{F}_p}$ from the get-go. The Frobenius map $x \mapsto x^p$ acts on the algebraic closure and its fixed points are precisely the roots of $x^p - x$, or the elements of $\mathbb{F}_p$. It follows that the orbits of the roots of a polynomial over $\mathbb{F}_p$ under the action of the Frobenius map are its irreducible factors.

Hence an element of $\overline{\mathbb{F}_p}$ is a root of an irreducible polynomial of degree $d$ if and only if it has order exactly $d$ under the Frobenius map, if and only if it divides $x^{p^d} - x$ and does not divide $x^{p^k} - x$ for $k < d$, if and only if it is contained in the fixed field of $x \mapsto x^{p^d}$ but not in the fixed field of $x \mapsto x^{p^k}$ for $k < d$. The fixed field of $x \mapsto x^{p^d}$ is a canonical copy of $\mathbb{F}_{p^d}$ inside the algebraic closure, and we have proven both (the correct version of) your statement and uniqueness of finite fields in one go.

Answer 2

C'est faux tel qu'énoncé. Il faut supposer le polynôme irréductible, auquel cas c'est vrai.

Si $P$ est irréductible sur $F_p$ et $P(\alpha) = 0$, alors $[F_p(\alpha):F_p] = \deg P = d$. Par conséquent, $F_p(\alpha) = F_{p^d}$, donc $\alpha \in F_{p^d}$.

Par contre, sur $F_3$, posons, $P(x) = (x^2 + 1)(x + 1)$. Si $\alpha^2 + 1 = 0$, on a $F_p(\alpha) = F_{9}$, qui n'est pas un sous-corps de $F_{27}$.

Answer 3

As Qiaochu Yuan said in his comment on the question, the claim

Given a polynomial with coefficients in GF$(p)$ and degree $d$, will that polynomial always have $d$ roots in GF$(p^d)$?

is false in general, but is true if the polynomial is irreducible over GF$(p)$.

The period of a polynomial $f(x)$ in GF$(q)[x]$, $q$ a prime power, is the smallest positive integer $e$ such that $f(x)$ is a divisor of $x^e - 1$. If $f(x)$ is the product of distinct irreducible polynomials, then $e$ is the least common multiple of the periods of the irreducible factors, and the smallest extension field of GF$(q)$ that contains all the roots of $f(x)$ is GF$(q^m)$ where $m$ is the smallest positive integer such that $x^e - 1$ is a divisor of $x^{q^m-1}-1$, equivalently, $e$ is a divisor of $q^m - 1$.

Theorem 6.21 in E. R. Berlekamp's Algebraic Coding Theory, McGraw-Hill 1968, gives the period of $f(x)$ in general.

If $f(x) = \prod_i [f^{(i)}(x)]^{m_i}$ where the $f^{(i)}(x)$ are irreducible polynomials of periods $n_i$ over GF$(q)$ of characteristic $p$, then the period of $f(x)$ is the least common multiple of the $n_i$ times the least power of $p$ which is not less than any of the $m_i$.

However, since the roots of $f(x)$ have multiplicities greater than $1$ if any of the $m_i$ is larger than $1$, the smallest field containing all the roots is determined by the period of $g(x) = \prod_i f^{(i)}(x)$ and this period is the least common multiple of the $n_i$.