A function h F F is said to be determined by a polynomial i

A function h : F F is said to be determined by a polynomial if there is some polynomial a(x) F[x] such that h(c) = a(c) for all c in F. Prove that if F is a finite field with n elements, then every function h : F F is determined by a polynomial of degree at most n

Solution

Let f(X) be any nonzero polynomial over F of degree n 1 or less. Then since
m(X) is irreducible and degf < degm, f(X) and m(X) are relatively prime, and there
are polynomials a(X) and b(X) over F such that a(X)f(X) + b(X)m(X) = 1. But
then a()f() = 1, so that any nonzero element of Fn1[] has a multiplicative inverse.
It follows that Fn1[] is a field. (This may not be obvious, since the product of two

polynomials of degree n1 or less can have degree greater than n1, but if degg > n1,
then divide g by m to get g(X) = q(X)m(X) + r(X) where deg r(X) < degm(X) = n.
Replace X by to get g() = r() Fn1[]. Less abstractly, if m() = 3 ++1 = 0,
then 3 = 1, 4 = 2 , and so on.)
Now any field containing F and must contain all polynomials in , in particular
all polynomials of degree at most n 1. Therefore Fn1[] F[] F(). But F()
is the smallest field containing F and , so F() Fn1[], and we conclude that
F() = F[] = Fn1[]. Finally, the elements 1, , . . . , n1 certainly span Fn1[], and
they are linearly independent because if a nontrivial linear combination of these elements
were zero, we would have a nonzero polynomial of degree less than that of m(X) with
as a root, contradicting (2) previous theorem
We now prove a basic multiplicativity result for extensions, after a preliminary discussion.

Suppose that F K E, the elements i, i I, form a basis for E over K, and the
elements j, j J, form a basis for K over F. (I and J need not be finite.) Then the
products ij, i I, j J, form a basis for E over F.
Proof. If E, then is a linear combination of the i with coefficients ai K, and
each ai is a linear combination of the j with coefficients bij F. It follows that the ij
span E over F. Now if i,j ijij = 0, then i iji = 0 for all j, and consequently
ij = 0 for all i, j, and the ij are linearly independent.
3.1.9 The Degree is Multiplicative
If F K E, then [E : F] = [E : K][K : F]. In particular, [E : F] is finite if and only if
[E : K] and [K : F] are both finite.
, we have [E : K] = |I|, [K : F] = |J|, and [E : F] = |I||J|.
We close this section by proving that every finite extension is algebraic.
If E is a finite extension of F, then E is an algebraic extension of F