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.

  • 2
    $\begingroup$ 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. $\endgroup$ – 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$.

  • 1
    $\begingroup$ 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. $\endgroup$ – Stefan Oct 29 '13 at 15:34
  • $\begingroup$ @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." $\endgroup$ – Thomas Andrews Oct 29 '13 at 17:08
  • $\begingroup$ 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! $\endgroup$ – Stefan Oct 29 '13 at 19:13
  • $\begingroup$ I probably should hav said "half of" rather than "the first part of..." :) @Stefan $\endgroup$ – Thomas Andrews Oct 29 '13 at 19:21
  • $\begingroup$ I can't prove the second half of (1) $\endgroup$ – MaudPieTheRocktorate Apr 20 '17 at 20:56

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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