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.
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.
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.
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}$.
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$.