Every Function in a Finite Field is a Polynomial Function 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$? 
 A: Hint: Vandermonde matrix.
A: 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$.  
A: Yes, your second method works and indeed generalizes nicely to functions in $n$ variables.
A similar method to show that every function $f: \mathbb{F}_q^n \rightarrow \mathbb{F}_q$ is given by a polynomial in which the degree in each variable is at most $q-1$ is to give an explicit polynomial formula for the "Dirac delta function" $\mathbb{1}_0(x)$ which is equal to $1$ if $x = (0,\ldots,0)$ and $0$ otherwise.  Indeed, we have
$\mathbb{1}_0(x_1,\ldots,x_n) = \prod_{i=1}^n (1-x_i^{q-1})$
as it is a pleasant and easy exercise to check.
Again a cardinality argument shows that any such function $f$ has a unique representation by a reduced polynomial, i.e., by a polynomial whose degree in each variable is at most $q-1$.  These observations lead quickly to a proof of the celebrated Chevalley-Warning Theorem: see these notes for a treatment of all these topics.
A: First off, a finite field doesn't necessarily have $p$ elements for $p$ prime. For every prime $p$ and natural number $m>0$ there is a finite field with $p^m$ elements.
Second, your approach is sound - the only piece you're missing is that your matrix is a Vandermonde matrix which, over any field, has a simple expression for its determinant.
A: There is a very simple argument based only on dimension and root counting. You want to show that the map$~g$ from the polynomials in $\def\Fq{{\Bbb F_q}}\Fq[X]$ to their polynomial functions in $\Fq^\Fq=\{\,f:\Fq\to\Fq\mid\,\}$ is surjective. It is easy to see the map is $\Fq$-linear and that $\dim(\Fq^\Fq)=q$. It is actually easier to show the stronger statement that the restriction$~\tilde g$ of$~g$ to the subspace $V=\{\,P\in\Fq[X]\mid\deg(P)<q\,\}$ is bijective (so in particular$~\tilde g$ is surjective, and a fortiori so is $g$).
Now $\dim(V)=q$ so$~\tilde g$ is a linear map between two vector spaces of the same dimension; such maps are bijective if and only if they are injective, i.e., have $\{0\}$ as kernel. Now $\ker(\tilde g)$ consists of those $P\in V$ whose polynomial function is the zero function. The part $P\in V$ means that $\deg(P)<q$, and the polynomial function being zero means that all $q$ elements of$~\Fq$ are roots of$~P$. It is well known that a nonzero polynomial over a field cannot have more roots than its degree. This shows that $\ker(\tilde g)=\{0\}$, so $\tilde g$ is bijective, as desired. 
