# 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$?

• $\alpha\in E$ is called algebraic over $F$, if there is a nonzero polynomial $f(x)\in F[x]$ such that $f(\alpha)=0$ in $E$. In this case, the minimum degree of polynomials $f$ with $f(\alpha)=0$ is called the degree of $\alpha$. We say $\alpha$ is an algebraic element over $F$ of degree $n$ if you can find a polynomial $f(x)\in F[x]$ of degree $n$ such that $f(\alpha)=0$ in $E$ and any other nonzero polynomial which annihilates $\alpha$ will have degree $\geq n$. One can show thatit is equivalent to there is an irreducible monic polynomial $f(x)$ of degree $n$ with $f(\alpha)=0$. – user119882 Mar 29 '14 at 4:33
• so how do I show $F(a)$ has $q^n$ elements? I never know how to use the field extension $E$ in this sort of problem.. – terrible at math Mar 29 '14 at 5:15
• You can show that $F(\alpha)=\{a_0+a_1\alpha+\cdots+a_{n-1}\alpha^{n-1}\mid a_i\in F\}$ and $a_0+a_1\alpha+\cdots+a_{n-1}\alpha^{n-1}\neq b_0+b_1\alpha+\cdots+b_{n-1}\alpha^{n-1}$ if coefficients $(a_0,\ldots,a_{n-1})\neq (b_0,\ldots,b_{n-1})$. – user119882 Mar 29 '14 at 9:25
• So our problem is how to show that $F(\alpha)=F[\alpha]$, to prove this you possbibly need the irredcubility of $f$ and $F[x]$ is a principal domain, etc. – user119882 Mar 29 '14 at 18:31
• Check out my answer. It in fact shows $F[a] = F(a)$ and, one way or the other, uses both the irreducibility of $f(x)$ and the fact that $F[x]$ is a PID! – Robert Lewis Mar 29 '14 at 22:26

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

• This is one hell of an answer, thanks! – terrible at math Mar 29 '14 at 23:14
• Hey! My pleasure, glad to help out! And thanks for the "acceptance"! – Robert Lewis Mar 29 '14 at 23:40

The statement "$a$ is algebraic over $F$ of degree $n$" means two things together:

1. $a$ is the root of some polynomial in $F[x]$ (that is, the coefficients of the polynomial lie in $F$) that has degree $n$.
2. 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{2}$ has degree $4$ over $\mathbb Q$.
• $\sqrt{2}$ has degree $2$ over $\mathbb Q(\sqrt{2})$.
• $\sqrt{2}$ has degree $1$ over $\mathbb Q(\sqrt{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?

• dimension and cardinality are equal there, right? in any case, how do I know that such a set forms a basis? or is it that obvious and I'm just not seeing it? – terrible at math Mar 29 '14 at 5:51
• No, dimension and cardinality are not equal --- just think of a field of $p$ elements, and a vector space of dimension 1; will that vector space have just 1 element? – Gerry Myerson Mar 29 '14 at 5:59
• oh no, it will have p elements :) – terrible at math Mar 29 '14 at 6:03
• @GerryMyerson so in the case we were talking about before, it's clear that we will have q^n elements just trying to figure out how to prove this.. – terrible at math Mar 29 '14 at 6:04