What's the exact definition of polynomial in $\mathbb{Z}_n$? I started learning some elementary number theory and encountered the following problem:
What's the exact definition of polynomial in $\mathbb{Z}_n$?
At first glance I had no problem, a polynomial in $\mathbb{Z}_n$ is a function $f:\mathbb{Z}_n \to \mathbb{Z}_n$ that can be represnted as:
$$f(x) = a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$$
But if this is the definition, what is the degree of $f(x) = x^p$ in $\mathbb{Z}_p$? On one hand it's $p$. On the other hand, by Euler's theorem, for every $x$, $f(x) = x$, so the degree is $1$. What is the correct answer?
Later I encountered the following proof to Wilson's theorem( $(p-1)!=-1 (mod \ p)$):
define $f:\mathbb{Z}_p \to \mathbb{Z}_p$ in the following way:
 $$f(x) = x^p-x$$
Notice that every $x \in \mathbb{Z}_p$ is a root of $f$ and then:
$$f(x) = x^p-x = x(x-1)(x-2)...(x-(p-1))$$
Now compare $x$'s coefficients on both sides and you'll get $(p-1)!=-1 (mod \ p)$ as required.
I find this proof very strange, since $f$ can also be represented as $f(x)= 2x^p - 2x$ and then we'll get $(p-1)!=-2 (mod \ p)$
I think that both problems I encounterd has the same root cause, and that is because I don't think I fully understand the definition and properties of polynomials in $\mathbb{Z}_n$.
Can anyone shed some light on the subject for me?
 A: A common way to formalize polynomials over some ring $R$ (commutative with identity, and let us say non-trivial to avoid some pathologies) is as sequences of elements in $R$ that are eventually $0$. 
More generally let us consider $R^{\mathbb{N}}$ the set of all sequences in $R$ and  $R^{(\mathbb{N})}$ the subset of sequences that are eventually $0$. 
So in the first the elements are  $(a_0, a_1, a_2, \dots)$ with $a_i \in R$ and in the latter one only has those sequences that from some point on have $a_i = 0$. 
Then defining $+$ coordinate-wise one gets a finite abelian group and 
one can define a multiplication operation by saying $(a_0, a_1, a_2, \dots)(b_0, b_1, b_2, \dots)$ is equal to $(c_0, c_1, c_2, \dots)$ where $c_i = \sum_{k+j=i}a_ib_j$. Then $R^{\mathbb{N}}$ becomes a ring and $R^{(\mathbb{N})}$ a subring. 
Now, interpret $(0,1, 0, \dots)$ as "the variable $X$" and you will see that $R^{(\mathbb{N})}$ with these operations "is" just the ring of polynomials. 
The other ring would be the ring of formal power-series.   
Thus, in some sense a polynomial is just its sequence of coefficients. 
As you remarked to think of polynomials as maps can lead to problems. 
It is true in full generality that to each polynomial one can associate a function $R$ to $R$, however this map $R[X] \to R^R$ is in general not injective (note that for a finite ring the latter is finite while the former is not). And, thus one cannot identify a polynomial with the function it induces. 
It is injective if and only of $R$ is an infinite domain. (Tangentially, it is surjective if and only if $R$ is a finite field.)
Thus, for example for the real numbers one indeed can identify polynomials with polynomial functions. Though, it is still useful to keep in mind that a polynomial is not in itself  a real function, but can be used to define one. 
On the specific point of the proof of Wilson's theorem, this is mainly addressed in anon's comment but let me frame it differently.
Since each element of $\mathbb{Z}_p$ is a root of the polynomial $X^p - X$ 
it follows that $(X-i) \mid X^p - X$ for each $i \in \mathbb{Z}_p$ [to proof this do polynomial division, and note the remainder must be $0$]
 and thus [as the factors are co-prime and we are in a UFD] $X(X-1) \dots (X- (p-1)) \mid X^p - X$. Thus for some polynomial $Q$ we have $QX(X-1) \dots (X- (p-1))=  X^p - X$. Yet, considering the degree we see that $Q$ is constant and comparing the leading coefficients we see that $Q=1$. Therefore $X(X-1) \dots (X- (p-1))=  X^p - X$.   
