Exercise 9, § 12

Let K be a finite field of q elements and let $r = q^n$ for an integer $n \geq 1$. For every polynomial $P(X) = \sum_{j=0}^m a_j X^j$ of $K[X]$, put

and

a) Show that if P, Q are two polynomials in $K[X]$ and if $R = PQ$, then we have $\tilde{R}(X) = \tilde{P}(\tilde{Q}(X))$. Deduce that for two polynomials F, G of $K[X]$ to be such that F divides G it is necessary and sufficient that $\hat{F}$ should divide $\hat{G}$. (To see that the condition is sufficient, consider the Euclidean division of G by F.) b) Let F be an irreducible polynomial in $K[X]$ and let G be any polynomial in $K[X]$. If there exists an integer d $\geq 1$ such that $\hat{F}(X^d)$ and $\hat{G}(X^d)$ have a common root, show that F divides G. (If H is the GCD of $\hat{F}(X^d)$ and $\hat{G}(X^d)$ consider the set of polynomials $P \in K[X]$ such that H divides $\hat{P}(X^d)$.) c) Every polynomial $F \neq 0$ of $K[X]$ divides a polynomial of the form $X^N - 1$. Show that if $r-1 = de$ and if $\alpha$ is a root of $\hat{F}(X^d)$, then a belongs to the extension K of degree $nN$ and deduce that the degree of every irreducible factor of $\hat{F}(X^d)$ in $K[X]$ divides $nN$ (use a)). If further e and $dN$ are relatively prime and if m is the degree of $\alpha$ over the extension of K of degree $n$, show that $m$ divides N (use the fact that $(r^N - 1)/e \equiv dN$ (mode)). d) With the notation as in c), suppose that F is irreducible and that N is the least of the integers h such that F divides $X^h - 1$. If e and $dN$ are relatively prime and if every prime factor of $n$ divides N, show that every irreducible factor of $\hat{F}(X^d)$ is of degree $nN$. (Note that in virtue of b) we then have $m = N$.) e) Deduce in particular from d) that if $P(X) = \sum_j a_j X^j$ is an irreducible polynomial in $K[X]$ and if N is the least of the integers h such that $P(X)$ divides $X^h - 1$, then every irreducible factor of $\sum u_j X^{q^j - 1}$ is of degree N.