Reading this Wikipedia page while learning about polynomials over finite fields, I came upon the following lemma:
For $i ≥ 1$ the polynomial $x^{q^i}-x \in \mathbf{F}_q[x]$ is the product of all monic irreducible polynomials in $\mathbf{F}_q[x]$ whose degree divides $i$.
What is this lemma properly called, and how is it proved?
On
See: Irreducible Polynomials over a Finite Field (search "splits" there)
With q prime, let $g(x)=x(x^{{q^i-1}}−1)$ , why every element of $F_{q^i}$ is a root of g(x) ?
My hint:
a) 0 is easy
b) $F_{q^i}-\{0\}$ is a cyclic multiplicative group of order ${q^i-1}$ so its elements satisfy $x^{{q^i-1}}−1=0$
c) g(x) has now every root it can afford !
The rest of the proof uses Galois theory (that's why "degree divides i" in your post and why the algorithm in the wiki you gave is fast enough).
I would like to say thanks to you : your post and the algorithm motivate me to learn more about Galois theory.
The proof is found in: https://www.jmilne.org/math/CourseNotes/FT.pdf
You should save that file and use Foxit to read it, then search for "Each monic irreducible polynomial f of degree" in the PDF.
PS: on SEP1993 (Fermat's Year), in the mad rush to Fermat's Last, after studying math for ca 70 days, I directly read the chapter "Galois theory" in Serge Lang book ("Algebra") using TOP-DOWN method : I went back to previous chapters if necessary. The method worked thanks to this legendary book which I borrowed from a layman-library!! Now a SEARCHable e-version can be had for < 20 USD, I think.
Hint for graduates: free PDFs : https://www.jmilne.org/math/CourseNotes/
Hints:
Denoting by $\;k:=\overline{\Bbb F_q}\;$ an algebraic closure of $\;\Bbb F_q\;$ , prove that for any $\;n\in\Bbb N\;$ we have that
$$\Bbb F_{q^n}=\left\{\;\alpha\in k\;:\;\;\alpha^{q^n}-\alpha=0\;\right\}$$
and now use/prove that $\;\Bbb F_{q^m}\le\Bbb F_{q^n}\;$ (the left field is a subfield of the right field) iff $\;m\le n\;,\;\;m,n\in\Bbb N$