Field extension of a finite field Let $E$ be an extension field of a finite field $F$ , where $F$ has $q$ elements. Let $a \in E$ be algebraic over $F$ of degree $n$. Prove that $F(a)$ has $q^n$ elements.
I am not sure how to do this one, but furthermore, what does $a$ being algebraic over $F$ of degree $n$ mean? Does it mean the polynomial $a$ solves in $F$ is of degree $n$?
 A: The statement "$a$ is algebraic over $F$ of degree $n$" means two things together:


*

*$a$ is the root of some polynomial in $F[x]$ (that is, the coefficients of the polynomial lie in $F$) that has degree $n$.

*Every other nonzero polynomial in $F[x]$ for which $a$ is a root has degree at least $n$.


In other words, the statement means that the minimal polynomial of $a$ over $F$ has degree $n$. For example, convince yourself that the following claims are true:


*

*$\sqrt[4]{2}$ has degree $4$ over $\mathbb Q$.

*$\sqrt[4]{2}$ has degree $2$ over $\mathbb Q(\sqrt{2})$.

*$\sqrt[4]{2}$ has degree $1$ over $\mathbb Q(\sqrt[4]{2})$.


Here's a second characterization of degree, one which you'll find useful in solving your problem. If $a$ is algebraic over $F$ of degree $n$ then the set $\{1,a,a^2,\dots,a^{n-1}\}$ forms a basis for the vector space $F(a)$. In other words, we can think of $F(a)$ as being a vector space over $F$ and the dimension of the vector space is the degree of $a$. For vector spaces over finite fields, what is the relationship between dimension and cardinality?
A: $a \in E$ is algebraic of degree $n$ over $F$ if there is a polynomial $f(x) \in F[x]$ with $\deg f = n$ and $f(a) = 0$ and there is no non-trivial polynomial $g(x) \in F[x]$ with $\deg g < \deg f$ and $g(a) = 0$.  It is easy to see we may assume $f(x)$ to be monic, that is the leading coefficient of $f(x)$ is $1$.  We point out that such an $f(x)$ must be irreducible in $F[x]$, for if $f(x) = f_1(x) f_2(x)$ with the $f_i(x)$ non-constant, then $0 = f(a) = f_1(a)f_2(a)$, so $f_j(a) = 0$ for least one of $j = 1, 2$.  But $\deg f_1, \deg f_2 < \deg f$, contradicting the minimality of $\deg f$ among polynomials $h(x)$ such that $h(a) = 0$.  We will revisit the irreducibility of $f$ in what follows.
This being said, consider the set $F(a) \subset E$.  Clearly $F(a)$ is a vector space over $F$; furthermore we have the elements $1, a, a^2, \ldots, a^{n - 1} \in F(a)$.  I claim they form a basis for the vector space $F(a)$.  For $F(a)$ is the smallest subfield of $E$ containing both $F$ and $a$; thus $p(a) \in F(a)$ for any $p(x) \in F[x]$, since $p(a)$ is formed by repeatedly applying the field operations of $E$ to $a$ and the coefficients of $p(x) = \sum_0^{\deg p} p_j x^j$, $p_j \in F$, $0 \le j \le \deg p$.  But by the division algorithm for polynomials, which holds in $F[x]$, we may write $p(x) = f(x)q(x) + r(x)$, where $q(x), r(x) \in F[x]$ and $\deg r < \deg f$.  Thus $p(a) = f(a)q(a) + r(a) = r(a)$ since $f(a) = 0$, showing that in fact $p(a)$ is always expressible as a polynomial in $a$ of degree less than $n$.  Furthermore, $(r(a))^{-1}$ is also given by $s(a)$ for some $s(x) \in F[x]$ with $\deg s < \deg f$.  To see this, we exploit the irreducibility of $f(x)$ shown in the above.  $f(x)$ irreducible implies $(f(x), r(x)) = 1$, since there is no non-constant $d(x) \in F[x]$ such that $d(x) \mid f(x)$;  $(f(x), r(x)) = 1$ implies that there are $g(x), s(x) \in F[x]$ with $g(x)f(x) + s(x)r(x) = 1$; evaluating at $a$ yields $s(a)r(a) = 1$ since $f(a) = 0$; by what we have seen, we may assume $\deg s < \deg f$.  These considerations conspire together to allow us to conclude that in fact the field $F(a)$ consists precisely of those elements of $E$ of the from $p(a)$, where $p(x) \in F[x]$ with $\deg p < \deg f$.  It is now clear that $\text{span} \{1, a, a^2, \ldots, a^{n - 1} \} = F(a)$; to show that $\{1, a, a^2, \ldots, a^{n - 1} \}$ is a basis, it merely remains to show its elements are linearly independent.  But if there are $c_i \in F$, $0 \le i \le n - 1$, not all zero, with $\sum_0^{n - 1} c_i a^i = 0$, then $a$ is a zero of the polynomial $c(x) = \sum_0^{n - 1} c_i x^i \in F[x]$; but $\deg c \le n - 1 < n = \deg f$, so we can rule out the existence of such a $c(x) \in F[x]$; thus we must have $c_i = 0$, $0 \le i \le n - 1$; the set $\{1, a, a^2, \ldots, a^{n - 1} \}$ is linearly independent and hence a basis for $F(a)$; every element of $F(a)$ may thus be uniquely written $\sum_0^{n - 1} c_i a^i$ for some suitable collection of $c_i \in F$, $1 \le i \le n - 1$.  But there are precisely $q$ choices for each $c_i$ which may be selected independently of one another; thus there are $q^n$ possible elements $\sum_0^{n - 1} c_i a^i$ in $F(a)$; $F(a)$ has precisely $q^n$ elements.  QED.
Hope this helps.  Cheerio,
and as always,
Fiat Lux!!!
