In a finite field $GF(p^n)$, is it true that $a^{1 + p + p^2 + ... + p^{n-1}}$ always belongs to $GF(p)$?

Question

Consider a finite field $F = GF({p^n})$, and $a \in F$ with $a \not = 0$.

How can we prove that $a^{1 + p + p^2 + ... + p^{n-1}}$ belongs to $GF(p)$?

This is a key fact of Itoh-Tsujii algorithm, but I cannot see why it's true -- the algorithm exploits the fact that $a^{1 + p + p^2 + ... + p^{n-1}}$ is just an integer mod $p$ instead of a "polynomial" in $GF({p^n})$ to reduce the inversion in $GF(p^n)$ to the simpler inversion in $GF({p})$.

Answer 1

Let $a \in \mathbb{F}_{p^{n}}$ be arbitrary and nonzero, and let $b = a^{1 + p + \cdots + p^{n-1}}$. We wish to show that $b$ is in $\mathbb{F}_{p}$. Note that $1 + p + \cdots + p^{n-1} = \frac{p^{n}-1}{p-1}$, so we have $$b^{p-1} = a^{p^{n}-1}.$$ However, since nonzero elements in $\mathbb{F}_{p^{n}}$ have multiplicative order $p^{n}-1$, it follows that $b^{p-1} = 1.$

In other words, $b$ is a root of the polynomial $x^{p-1} -1$. We know that each of the $p-1$ nonzero elements of $\mathbb{F}_{p}$ are roots of the polynomial. Furthermore, since this polynomial has degree $p-1$, it has at most $p-1$ roots, hence the $p-1$ nonzero elements of $\mathbb{F}_{p}$ the only roots of this polynomial. It follows that $b$ is a nonzero element of $\mathbb{F}_{p}$, as desired.

Answer 2

In $GF(p^n)$ you can see $GF(p)$ as the set of all solutions of the equation $x^{p-1}=1$, together with zero.

Thus, if $x=a^{1+p+\ldots+p^{n-1}}=0$ we are done. If not, then $a\ne 0$ itself. In that case:

$$x^{p-1}=a^{(p-1)(1+p+\ldots+p^{n-1})}=a^{p^n-1}=1$$

so $x$ is in $GF(p)$.