Product of all irreducibles with degree divisible by $n$ in $\mathbb{F}_{q^n}$?

In the finite field of $q^n$ elements, the product of all monic irreducible polynomials with degree dividing $n$ is known to simply be $X^{q^n}-X$. Why is this?

I understand that $q^n=\sum_{d\mid n}dm_d(q)$, where $m_d(q)$ is the number of irreducible monic polynomials with degree $d$, and that each element of the field satisfies $X^{q^n}-X$.

How does the conclusion follow from this? I tried substituting the exponent to $X^{\sum_{d\mid n}dm_d(q)}-X$ but this doesn't seem to do much good.

-
Your first $q^n$ should be $q$. The product of all monic irreducible polynomials of degree dividing $n$ over the field of $q^n$ elements is $X^{(q^n)^n}-X$: there are at least $q^n$ of degree $1$, and you also have irreducibles of degree $n$, among others. –  Arturo Magidin Feb 7 '12 at 17:07

Let $\mathbf{F}$ be the field of $q$ elements, and fix $n\geq 1$. The extension of degree $n$ over $\mathbf{F}$ is the field with $q^n$ elements. Call that $\mathbf{K}$.

If $a\in\mathbf{K}$, then $\mathbf{F}(a)$ is an intermediate field, so $[\mathbf{F}(a):\mathbf{F}]$ divides $n$; that is, the monic irreducible polynomial of $a$ is of degree dividing $n$ over $\mathbf{F}$. So every element corresponds to a monic irreducible.

Moreover, every monic irreducible of degree dividing $n$ corresponds to an element in $\mathbf{K}$: if $f(x)$ is such an irreducible, and $a$ is a root, then $\mathbf{F}(a)$ has degree $\deg(f)$, which divides $n$, and so is contained in the field extension of degree $n$ (remember that $\mathbf{F}_{q^r}\subseteq \mathbf{F}_{q^s}$ if and only if $r|s$).

That means that if you let $P(X)$ be the product of all monic irreducible polynomials over $\mathbf{F}$ that have degree dividing $n$, then its roots are precisely the elements of $\mathbf{K}$.

We also know that $\mathbf{K}$ is the splitting field of $X^{q^n}-X$: every element of $\mathbf{K}$ satisfies this polynomial (by Lagrange's Theorem, every nonzero element satisfies $a^{q^n-1}=1$, and then there's $0$), and no field strictly smaller than $\mathbf{K}$ can be the splitting field (not enough roots). So now we have two polynomials that are satisfied by every element of $\mathbf{K}$ and only by all the elements of $\mathbf{K}$: $X^{q^n}-X$ and our $P(X)$. So $X^{q^n}-X$ certainly must divide $P(X)$, and $P(X)$ must be a product of linear factors over $\mathbf{K}$.

So the only question that remains is: does $P(X)$ have any repeated roots?

-

As noted by Arturo, the problem should be stated about $\mathbb F_q$, not $\mathbb F_{q^n}$.

There are two steps here.

1. Prove that a prime $\pi(x)$ in $\mathbb F_q[x]$ divides $x^{q^n}-x$ if and only if $\deg(\pi(x))\mid n$
2. Prove that there are no repeated prime factors of $x^{q^n}-x$.

First prove that for integers $d,n$, $x^{q^d}-x|x^{q^n}-x$ if and only if $d\mid n$.

I'll prove the first part of (1) for you. If $\deg(\pi(x))=d$, and $d|n$ then consider the field $F=\mathbb F_q[x]\big /{\left<\pi(x)\right>}$. It is of order $q^d$, so we know that for every element $y\in F$, $y^{q^d}=y$. In particular, $x$ is an element of $\mathbb F_q[x]$, so the image $\bar x$ of $x$ in $F$ has the property that ${\bar x}^{q^d}-\bar{x}=0$. But that means that the image of $x^{q^d}-x$ is in the kernel of the map from $\mathbb F_p[x]$ to $F$. So $x^{q^d}-x$ is divisible by $\pi(x)$. So, by our first step above, $x^{q^n}-x$ is divisible by $\pi(x)$ when $d|n$.

-
It could be that $\pi ~|~ x^{x^n}-x$ but not $x^{q^d}-x ~|~ x^{q^n}-x$, so it doesn't follow that $d ~|~ n$ as far as I can see. –  Stefan Oct 29 '13 at 15:34
@Stefan I said the first part of (1). Note the sentence, "If $\deg =d$ and $d\mid n$. I did not try to prove the other part of the "if and only if." –  Thomas Andrews Oct 29 '13 at 17:08
Ah yes, that explains it. I got a little bit confused why you asked to prove "$d,n$, $x^{q^d}-x|x^{q^n}-x$ if and only if $d|n$" first, as you only need the $\Leftarrow$ part for the first part of (1). Thanks! –  Stefan Oct 29 '13 at 19:13
I probably should hav said "half of" rather than "the first part of..." :) @Stefan –  Thomas Andrews Oct 29 '13 at 19:21

Show that $\large X^{q^n}−X \in \mathbb{F}_q[X]$ (with $q = p^k$ for some prime $p \in \mathbb{N}^+$ and $k,n \in \mathbb{N}^+$) is the product of all monic irreducible polynomials $\pi \in \mathbb{F}_q[X]$ with $\deg(\pi) ~|~ n$:

Lemma 1:

$\forall q, n, d \in \mathbb{N}^+: \large q^n \bmod \left(q^d-1\right) = q^{n ~\bmod~ d}$ as $q^d = 1 \bmod \left(q^d-1\right)$

Lemma 2:

$\large \gcd\left(X^{q^n} - X, X^{q^d} - X\right) = X^{q^{\gcd(n, d)}} - X$
(in any polynomial ring over a field, especially in $\mathbb{F}_q[X]$)

For $n = d$ this is obvious, assume w.l.o.g. $n > d$. For all $1 \leq k \in \mathbb{N}$ with $q^n - k(q^d-1) > 0$ (required so all exponents are $\geq 0$):

$$\large X^{q^n} - X = \left(\sum\limits_{i=1}^k X^{q^n -i(q^d-1) - 1}\right)\cdot \left(X^{q^d}-X\right) + \left(X^{q^n -k(q^d-1)} - X\right)$$

As $q^n \bmod \left(q^d-1\right) = q^{n ~\bmod~ d} \neq 0$ ($\exists k: q^n \bmod \left(q^d-1\right) = q^n - k(q^d-1) > 0$):

$$\large \Rightarrow \left(\large X^{q^n} - X\right) \bmod \left(X^{q^d}-X\right) = \left(X^{q^{n ~\bmod~ d}} - X\right)$$

$$\large \Rightarrow \gcd\left(X^{q^n} - X, X^{q^d} - X\right) = \gcd\left(X^{q^d} - X, X^{q^{n ~\bmod~ d}} - X\right)$$

I.e. the $\gcd$ modulo reduction is done in the $q$ and $d$ exponents.

Step 1: (Similar to the answer by Thomas Andrews)

Let $\pi$ be a monic irreducible polynomial in $\mathbb{F}_q[X]$ with degree $d = \deg(\pi)$, and $F_{\pi} := \mathbb{F}_q[X]/\left<\pi\right>$ with $\varphi: \mathbb{F}_q[X] \to F_{\pi}$. Show $d ~|~ n \Rightarrow \pi ~|~ \left(X^{q^n}-X\right)$.

As the size of the multiplicative subgroup $\large \left|F_{\pi}^\ast\right| = q^d-1$, it follows that $\large\forall y \in F_{\pi}: y^{q^d-1} = 1, y^{q^d} - y = 0$. $\large y^{q^d} - y = 0$ is also true for $\large y = 0$, i.e. $\large\forall y \in F_{\pi}$.

Therefore $\large \varphi(X^{q^d}-X) = 0 \Rightarrow \exists k \in \mathbb{F}_q[X]: \left(X^{q^d}-X\right) = 0 + k \cdot \pi \Rightarrow \pi ~|~ \left(X^{q^d}-X\right)$

If $d ~|~ n \Rightarrow \large \gcd\left(X^{q^n} - X, X^{q^d} - X\right) = X^{q^d} - X \Rightarrow \pi ~|~ \left(X^{q^n} - X\right)$

Step 2:

$\large f = X^{q^n} - X \in \mathbb{F}_q[X]$ is square-free, as $\large f' = q^n \cdot X^{q^n-1} - 1 = -1$ ($q = 0$ in $\mathbb{F}_q$!), and $\gcd(f, f') = 1$.

If $\exists a, b \in \mathbb{F}_q[X]: f = (a \cdot a) \cdot b$
$\Rightarrow f' = (a\cdot a' + a' \cdot a) \cdot b + (a \cdot a) \cdot b' = a \cdot (a'\cdot b + a'\cdot b + a \cdot b')$
$\Rightarrow a ~|~ \gcd(f, f')$

As $\gcd(f, f') = 1$ there is no $a \in \mathbb{F}_q[X]$ with $\deg(a) \geq 1$ and $a ~|~ \gcd(f, f')$, and $f$ is square-free.

Step 3:

Induction over $n \geq 1$: show that $\large p_n := X^{q^n} - X \in \mathbb{F}_q[X]$ is the product of all monic irreducible polynomials $\pi \in \mathbb{F}_q[X]$ with $\deg(\pi) ~|~ n$.

We already know that all such $\pi$ are factors of $p_n$ and $p_n$ is square free. Now show that all factors have the required form.

Let $\pi \in \mathbb{F}_q[X]$ be a irreducible polynomial with $d = \deg(\pi)$ and $\pi ~|~ p_n$. Then $\pi ~|~ \gcd(p_n, p_d) = p_{\gcd(n, d)}$.

If $\gcd(n, d) < d$ then (by induction) $\pi \nmid p_{\gcd(n, d)}$ as $d \nmid n$.

Otherwise $\gcd(n, d) = d \Rightarrow d ~|~ n$.

-