0
$\begingroup$

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.

  • 7
    No, this is false i$n$ general. It is true if the polynomial is irreducible by uniqueness of finite fields or more generally true if the irreducible factors all have degree dividing d.2011-02-08

3 Answers 3

6

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.

  • 0
    @kahen E. R. Berlekamp's _Algebraic Coding Theory,_ McGraw-Hill 1968 uses the _notation_ GF$(p^{\infty!})$ for the algebraic closure of GF$(p)$. Berlekamp did not use $F_p$ or $\mathbb F_p$ (as is common on math.SE) in his book. Nor did he need to use the notion of algebraic closure very much.2012-01-11
1

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

  • 1
    **To all**: we should probably adjourn to meta for further discussion of this issue.2011-02-08
1

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