Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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 \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!!!
The statement "$a$ is algebraic over $F$ of degree $n$" means two things together:
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:
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?
