Exercise 11.2.15

Proof.

(a)

Let $\gamma$ a generator of the cyclic group ${𝔽}_{p^n}^{\text{∗}}$, with cardinality $p^n-1$. Then ${\gamma }^k,0\le k<p^n-1$, is a generator of the same group if and only if $k\wedge n=1$, so ${𝔽}_{p^n}$ has $\varphi (p^n-1)$ primitive roots.

(b)

Let $\alpha$ be a primitive root of ${𝔽}_{p^n}$. As $F_{p^n}=\{0\}\cup \{1,\alpha ,{\alpha }^2,\dots ,{\alpha }^{p^n-2}\}$, then ${𝔽}_{p^n}={𝔽}_p(\alpha )$ (in other words, a primitive root of ${𝔽}_{p^n}$ is a primitive element of the extension ${𝔽}_p\subset {𝔽}_{p^n}$).

Let $f$ be a primitive polynomial. By definition, $f$ is the minimal polynomial of a primitive root $\alpha$. Then

$$\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(f)=[{𝔽}_p(\alpha ):{𝔽}_p]=[{𝔽}_{p^n}:{𝔽}_p]=n.$$

Every primitive polynomial for ${𝔽}_{p^n}$ has degree $n$.

(c)

By definition of the cyclotomic polynomials (and Proposition 11.2.6), $${\Phi }_{p^n-1}(x)=\underset{o(\alpha )=p^n-1}{\prod }(x-\alpha ),$$

where we write $o(\alpha )$ the order of $\alpha$ in the group ${𝔽}_{p^n}^{\text{∗}}$.

So the roots of ${\Phi }_{p^n-1}(x)$ are the primitive roots of ${𝔽}_{p^n}$.

Let $f$ be a primitive polynomial for ${𝔽}_{p^n}$. By definition , $f$ is the minimal polynomial of some primitive root $\alpha$ of ${𝔽}_{p^n}$. Since ${\Phi }_{p^n-1}(\alpha )=0$, $f$ divides ${\Phi }_{p^n-1}(x)$.

Conversely, let $f\in {𝔽}_p[x]$ be an irreducible factor of ${\Phi }_{p^n-1}(x)$. Let $\alpha$ be a root of $f(x)$ in some extension of ${𝔽}_{p^n}$. Since $f(x)\mid {\Phi }_{p^n-1}(x)$ and ${\Phi }_{p^n-1}(x)\mid x^{p^n-1}-1$, then ${\alpha }^{p^n-1}=1$, ${\alpha }^{p^n}=\alpha$, therefore $\alpha \in {𝔽}_{p^n}$. Moreover $\alpha$ is a root of ${\Phi }_{p^n-1}(x)$, so $\alpha$ is a primitive root of ${𝔽}_{p^n}$, thus $f$ is a primitive polynomial for ${𝔽}_{p^n}$.

So the irreducible factors of ${\Phi }_{p^n-1}(x)$ in ${𝔽}_p[x]$ are all primitive polynomials for ${𝔽}_{p^n}$. Since ${\Phi }_{p^n-1}(x)$ is a separable polynomial, ${\Phi }_{p^n-1}(x)$ is squarefree, so ${\Phi }_{p^n-1}(x)$ is the product of its monic irreducible factors:

the product of the primitive polynomials for ${𝔽}_{p^n}$ is ${\Phi }_{p^n-1}(x)$.

Note: this is consistent with Theorem 11.2.7. Indeed, ${\Phi }_{p^n-1}(x)$ is the product of irreducible polynomials in ${𝔽}_p[x]$ of degree $m$, where $m$ is the minimum of the integers $k$ such that $d=p^n-1\mid p^k-1$, so $m=n$ (the order of $p$ modulo $p^n-1$ is $n$). Here we have proved that these factors are the primitive polynomials for ${𝔽}_{p^n}$.