From a bank of past master's exams I am going through:
Let $F$ be a finite field. Show that any function from $F$ to $F$ is a polynomial function.
I know that finite fields are fields of $p$ elements for $p$ prime [EDIT: It's actually $p^n$ for $p$ prime; see comment below]. Since I have $p$ choices for the $p$ elements to map to, then I have $p^p$ distinct functions. I think every function can be written in the form $f(x) = a_{p-1}x^{p-1} + \dots + a_0x^0$. For then given the values $f(0), f(1), \ldots f(p-1)$, I can solve for the coefficents by the linear system of equations
$$ a_0 + \sum_{i=1}^{p-1} n^i a_i = f(n).$$
This then gives me a $p-1 \times p-1$ square matrix over the field $\mathbb{F}_p$:
$$\left( \begin{array}{ccccc}
1& 0 & 0 & \ldots & 0 \\
1& 1 & 1 & \dots & 1 \\
1& 2 & 4 & \dots & 2^{p-1} \\
\vdots & \vdots & \vdots & & \vdots \\
1 & p-1 & (p-1)^2 & \dots & (p-1)^{p-1}
\end{array} \right)
\left( \begin{array}{c}
a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{p-1}
\end{array}\right)
=
\left( \begin{array}{c}
f(0) \\ f(1) \\ f(2) \\ \vdots \\ f(p-1)
\end{array} \right)$$
If I can show this matrix is invertible, then I can always find the $a_i$. But I am a bit stumped on how to show this (partially because I don't think I've ever done linear algebra in a vector space over a finite field). It does not seem easy to show linear independence, or nonzero determinant, or full row rank.
Alternatively (I just thought of this), can I show this is true by arguing that the map between the two sets (the set of polynomials of degree $p-1$; and the set of functions $F \to F$) is injective, and that it must be a bijection because the sets have the same cardinality $p^p$?
Best Answer
It might be interesting to you to look up the Lagrange Interpolation Formula. Given a function $f$ from the finite field to itself, it will give you an explicit polynomial $P$ such that the associated polynomial function is equal to $f$.