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. 
 A: 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.
A: You’re confusing the function defined by a polynomial with the polynomial itself, which is just a formal sum of the powers of a variable. Even over the finite field $\Bbb F_p$, the polynomial $x^p-x$ , which is indeed identically zero on the field $\Bbb F_p$, is still a nonzero polynomial. 
A: There is a basis of the vector space of the polynomials (in one variable) over any field ... and it is $1, x, x^2, x^3, \ldots$
This is because polynomials are not functions - they are expressions (in a loose sense, e.g. see https://en.wikipedia.org/wiki/Polynomial_ring. This can be formalised in different ways). The main point is that two polynomials are considered equal if and only if all their corresponding coefficients are equal. Thus any finite subset of $\{1, x, x^2, x^3, \ldots\}$ is linearly independent - and obviously every polynomial is a (finite) linear combination of $1, x, x^2, x^3$ etc.
This is all valid regardless of what happens later if you try to substitute the "variable" (symbol) $x$ by elements from the field. In your example, the polynomial $x^2+x$ is nonzero in $\mathbb Z_2[x]$, even if the value of it is zero for each $x\in\mathbb Z_2$.
There is a different concept of a polynomial function, which is the function calculated by a (polynomial) expression. For example, $f(x)=x^2+x$ is a function $f:\mathbb Z_2\to\mathbb Z_2$ and, as a function, it is equal to the zero function. Two different polynomials, as you can see ($0$ and $x^2+x$ from $\mathbb Z_2[x]$) provide you with the same polynomial function.
However, this can happen precisely when the field is finite:


*

*For a finite field $F$ with $q$ elements, the $q-1$ invertible elements make up a (commutative) group with respect to multiplication, so the order of every element divides the order of the group (Lagrange's theorem), i.e. for each $x\in F\setminus\{0\}$ we have $x^{q-1}=1$. By multiplying by $x$, one easily derives from this that, for each $x\in F$, $x^q=x$, so the polynomial $x^q-x$ has a zero function as its polynomial function, even if the polynomial itself is nonzero.

*For an infinite field $F$, two different polynomials must provide for two different polynomial functions. Otherwise, their difference would vanish (i.e. have a zero) at every element of the field. Then it easily follows that the difference itself (as a polynomial) is zero. (A nonzero polynomial can have at most as many zeros as its degree!)
A: 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.
