Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
No, this is false in 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. –  Qiaochu Yuan Feb 8 '11 at 10:01

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
    
If I recall correctly, the smallest algebraically closed field containing $F_p$ is commonly written as "$F_{p^\infty}$" and one way of realising it is as the inverse limit of $F_{p^{n!}}$ –  kahen Feb 8 '11 at 12:41
    
@kahen: I've never seen anyone use that notation. It seems unnecessary when there is already a perfectly good general notation for algebraic closures. The algebraic closure of F_p is also not an inverse limit; it is a direct limit, or colimit. –  Qiaochu Yuan Feb 8 '11 at 12:50
    
You're right. I think I made a thinko there –  kahen Feb 8 '11 at 13:01
    
Very nice, except the last two if and only ifs aren't quite right: for example $\mathbb{F}_p$ is contained in the fixed field of $x\mapsto x^{p^d}$. I think for both of those statements you want to add something like "$d$ is the smallest number such that". –  Noah Stein Feb 8 '11 at 23:30
    
@Noah: whoops, you're right. Fixed. –  Qiaochu Yuan Feb 8 '11 at 23:32

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

share|improve this answer
4  
It seems reasonable to me to ask questions in whatever language you wish (taking what responses you get). But when a question is asked in English on a heretofore English-language website, how is it helpful to reply in another language? If no one in the English speaking world could answer the question, that would be one thing, but that doesn't seem to be the case here. –  Pete L. Clark Feb 8 '11 at 10:17
2  
Peut-être en fournissant une réponse plus rapide? De plus, même s'il y a beaucoup de monde capable d'y répondre, on ne peut pas savoir si quelqu'un d'autre va prendre le temps de donner une réponse détaillée. Comment est-ce que ça peut faire du mal? –  user6780 Feb 8 '11 at 10:30
1  
Il n'y a aucune de raison de présupposer que tout le monde comprend le français et si vous le faites, il est arrogant. Si vous essayer d'aider, vous devriez au moins demander si la personne qui avait poser la question sait lire une réponse en français avant de répondre. Dans votre question, vous avez remarqué "Vous pouvez répondre dans une autre langue.", mais il n'y a pas de telles indications dans la présente question. –  Alex B. Feb 8 '11 at 11:35
4  
R.: <<Comment est-ce que ça peut faire du mal?>> Here's how: the sort of professional mathematician that actively answers questions on this site is much more likely to have a decent reading knowledge of French than a student who is asking questions, especially at the undergraduate level. If you leave an answer in French that the experts can read and see is correct, this could well dissuade them from leaving an English answer. Then the OP is left with an answer that others say is correct but s/he can't read! –  Pete L. Clark Feb 8 '11 at 11:52
1  
To all: we should probably adjourn to meta for further discussion of this issue. –  Pete L. Clark Feb 8 '11 at 12:00

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.