Can all functions over $\mathbb{Z}/4\mathbb{Z}$ be "described" by a polynomial? Consider the set $T$ of functions from $\mathbb{Z}/4\mathbb{Z}$ to $\mathbb{Z}/4\mathbb{Z}$. I'm now asked to prove or disprove the statement that all functions in $T$ can be described by a polynomial over $\mathbb{Z}/4\mathbb{Z}$, i.e. for any $f \in T$, there exists a polynomial $P \in (\mathbb{Z}/4\mathbb{Z})[X]$ so that the polynomial function for $P$ takes exactly the values that $f$ takes.
I already know that this statement is true if instead of $\mathbb{Z}/4\mathbb{Z}$, we have a finite field as the underlying structure, but since $\mathbb{Z}/4\mathbb{Z}$ is not a field, I rather suspect that this statement is not true, i.e. that there is any function that gets in our way. If I suspect that I have found such a function, I would need to show that no polynomial over $\mathbb{Z}/4\mathbb{Z}$ takes the same values as $f$.
I guess that there is a simple counterexample, but so far, I haven't been able to find one. Obviously we can't use any constant function, but I'm so far out of ideas what I can do to construct such a counterexample.
 A: Any polynomial function will have the property that $x \equiv y \pmod 2 \implies f(x) \equiv f(y) \pmod 2$.
On the other hand it is easy to give an example of a function that doesn't have it.
A: Another way to look at it is by just counting. We have that $n^4 = n^2$ for any $n$, so any polynomial function may be represented by a polynomial of degree $3$ or less. There are $4^4$ polynomials of degree three or less, and there are $4^4$ functions in $T$. However, there is some overlap between the polynomials, since for instance the polynomial expressions 
$$
2n + 2n^2\\
2n + 2n^3\\
0
$$
represent the same function. Therefore there must be some functions that cannot be polynomials.
A: Let $R$ be a commutative ring with $1$. If every function from $R$ to $R$ is a polynomial then every non-zero $r\in R$ is invertible. 
To wit,  a function $f$ with $f(0)= 0$ and $f(r)=1$. Suppose it is polynomial. 
Then the polynomial has no constant coefficient, because $f(0)=0$. Yet, then $f(r)= rg(r)$ for some $g(r) \in R$, and also $f(r)=1$, so $r$ is invertible.  
Indeed, this leads to every function from $R$ to $R$ is a polynomial if and only of $R$ is a finite field.
A: Consider a polynomial $p(X) = \sum_{k=0}^n a_k X^k$ with $a_k \in \mathbb{Z}/4\mathbb{Z}$. Then we have
$$ p(0) = a_0, \\
   p(2) = a_0 + a_1 \cdot 2 + a_2 2^2 + \dots + a_n 2^n = a_0 + 2a_1. $$
Hence, we can't find a polynomial that satisfies for example $p(0) = 1, p(2) = 2$ as the equation $2a_1 = 1$ has no solution in $\mathbb{Z}/4\mathbb{Z}$.
A: Hint $\, $ If so there is a polynomial with $f(\color{#0a0}2)=0,\,f(0)=\color{#c00}1.\,$ Therefore, by the Factor Theorem, the root $\,\color{#0a0}2\,$ divides  the constant term $\color{#c00}1,\,$ i.e. $\,2a = 1,\,$ so $\,2\,$ is invertible, contra $\,2\cdot 2 = 0$.
Remark $\ $ Thus, if so, every nonzero element is invertible, i.e. the ring is a field.
Many nice proofs arise by exploiting relationships between the factorizations of polynomials and the factorization of the values they take. For example, one can devise a simple algorithm for polynomial factorization using factorization of its integer values and Lagrange interpolation. The ideas behind this algorithm are due in part to Bernoulli, Schubert, Kronecker. 
