Polynomial $P$ over a finite field $F_{q}$ I've just started with the theory of finite fields and I am stuck in an exercise, which must be not so difficult... Can anybody, please, give me a hint what can I do for to solve it?
Given is a finite field $F_{q}$ with $q$ elements, not necesserily prime and a function $f:F_{q}\rightarrow F_{q}$.

Prove that there exists a polynomial $P\in F_{q}[x]$, such that $P(x)=f(x)$ for every $x\in F_{q}$.
I would be glad, if someone could help me. Thank you in advance!
 A: Try to find a polynomial that is zero everywhere except at one point $x \in F_q$. This is possible because the field is finite. The solution is a linear combination of such polynomials.
A: Hint: For $\alpha \in \mathbb{F}_q$, first construct a polynomial $f_\alpha$ such that $f_\alpha(\alpha) \neq 0$ and $f_\alpha(\beta) = 0$ for all $\beta \neq \alpha$. Once this is done, you can in fact make it so $f_\alpha(\alpha) = 1$. Then the general polynomial can be made by taking a sum over the $f_\alpha$ with appropriate coefficients.
A: Hint:  If you are familiar with the term, Lagrange Interpolating Polynomial solves the problem.
Otherwise, let $P(X)=a_nX^n+...+a_1x+a_0$ where we will chose $n$ later (I can chose it now, but the value will become obvious later).
Setting 
$$P(a)=f(a) \forall a \in F_q $$
is a system of $q$ equations with the $n+1$ unknowns $a_0,...,a_n$. Thus if $n+1=q$ we get a square system, where the determinant can be proven to be  non-zero (is actually a Vandermonde determinant). Pick the unique solution.
A: Hint: the set of nonzero elements of $\mathbb F_q$ is a group of order $q-1$. So all nonzero elements are roots of $X^{q-1}-1$. Then?
A: Whilst staring at my laptop's screen in t'shuvah  for my most blasphemous comment, grace found me, fiat lux!!!:
Let $F_q = \{a_1, a_2, . . . , a_q\}$; the $a_i$ are the distinct elements of $F_q$.
Set 
$p_i(x) = f(a_i) \frac{\prod_{j \ne i}(x - a_j)}{\prod_{j \ne i}(a_i - a_j)}, \tag{1}$
then
$p_i(a_i) = f(a_i), \tag{2}$
and if $i \ne j$,
$p_i(a_j) = 0. \tag{3}$
So if we set
$P(x) = \sum_i p_i(x) \tag{4}$
it is easy to see that 
$P(a_i) = f(a_i) \tag{5}$
for all $a_i \in F_q$, where as I have recently learned $F_q$ is a finite field with
$q = p^n$ elements for some prime $p$!
Now, correct me if I'm wrong, did I not just rediscover (something perilously close to)
Lagrange interpolation?
Ah, sweet forgiveness!
Peace, Love, and chag s'meach
But above all, 
Fiat Lux!!!
