The Linear Independence of Powers of x over finite fields My professor asked us to prove that $P =\{1,x,x^2,\dots, x^n \dots \}$ is a basis for polynomials. This is pretty simple if you are working over $\mathbb{R}$, however he did not specify which field (though it was clear he meant $\mathbb{R}$). 

In order for $P$ to be a basis, its elements must be linearly independent. 
This is easy to prove over an infinite field, by finitely many roots. However, $P$ is not necessarily linearly independent over finite fields. For instance, in $\mathbb{Z}_2$, $x^n + x = 0$ for all $x$.

My question is if there is a basis for all polynomials over a finite field? My abstract algebra is weak and this was just something I noticed in my introductory linear algebra course.
This is a frequent point of confusion.  

It is true that, say, $x^3$ and $x$ take the same values $\pmod 3$ as $x$ runs through the residues $\pmod 3$.  However, they are not the same polynomial.  Two polynomials $\sum_{i=0}^na_ix^i$ and $\sum_{i=0}^{m}b_ix^i$ are said to be the same if and only if $a_i=b_i$ for all $i$.  Note that this implies that the degrees are the same.  

With this definition, the linear independence of the monomials $\{x^i\}$ is clear.

As a partial justification of this definition, note that, while $x^3$ and $x$ take the same values in the finite field $\mathbb F_3$, they take different values in extension fields, $\mathbb F_9$ for instance.  Indeed, by the usual results from field theory, the polynomial $x^3-x$ could only have at most three roots in any field.
The definition of an $n$-dimensional vector space, $V$ is that any vector $u \in V$ can be written as a linear combination of the space's basis vectors and that no linear combination of these basis vectors is in the nullspace of $V$. 

Let the set of vectors $S =  \{u_1, ..., u_n \}$, by definition of linear independence then $S \subset  span\{U\}$ iff $U$ is at least $n$ dimensional.