Given the set of integers modulo $n$, can all functions from this set to itself be expressed as polynomials? For a given $n$ is there a guaranteed way to construct any possible function from $\mathbb{Z}/n\mathbb{Z}$ to itself in terms of polynomials? Specifically, for $T = \mathbb{Z}/n\mathbb{Z}$ I'd like to use polynomials with $T$ coefficients to describe all functions $T \to T$.
My original hypothesis was that I could express functions $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ as a polynomial of order $n$ or less with coefficients in $\mathbb{Z}/n\mathbb{Z}$. I determined that this was true for $n=1, 2, 3, 5, 7$ (using brute force) but that it was false for $n=4, 6$. My new hypothesis is that it may only be true for prime $n$ (but I can't use brute force to test $11$ or larger primes).
Is this true for all prime $n$? If so, is there a more general result I can use for composite $n$? If not, are there other approaches I could use? Is this impossible in general?
One idea I had for composite $n$ was to use the prime factorization of $n$ ($p_0^{k_0}p_1^{k_1}...$) to construct polynomials for all the factors and then combine them into a single multivariate polynomial. I was able to do this for $n=4$ ($2^2$) by constructing $axy + bx + cy + d$ for $x, y \in [0, 1]$ and $a, b, c, d \in [0, 3]$. But I wasn't able to adapt this approach to $n=6$.
I'm interested in programmatically generating an enumeration of all possible functions $T \to T$ in terms of a given enumeration of $T$. Since the cardinality of this set is $|T|^{|T|}$ I won't actually generate most of these functions. The important part is that I have a mapping from each $index$ to a distinct function, and that in principle there is an $index$ for every possible function (even if some indices are far too large to work with). I'm doing this in a software library that already contains enumeration strategies for many other data structures such as lists, tuples, sets, maps, and so on.
I have an existing solution that uses tables to map a subset of inputs to non-zero outputs (mapping all other inputs to zero). I can show that my enumeration constructs every possible table (eventually) so that in principle every function can be represented (although for data structures like 32-bit integers most interesting functions such as $f(x) = x + 1$ would have tables far too big to be useful). However most enumerations for small $index$ values are uninteresting (they produce zero for most inputs).
I was hoping to generate polynomials instead of tables, since even relatively simple polynomials would have more interesting behaviors. But I can't do this unless I know a way to construct a set of polynomials that represents each possible function exactly once.
 A: The 1995 paper On polynomial functions from $\mathbb{Z}_n$  to $\mathbb{Z}_m$ in Discrete Mathematics, Vol. 137, proves the following strongly related result:
Theorem: Every function $f:\mathbb{Z}_n \rightarrow \mathbb{Z}_m$ is a polynomial function if and only if $n$ is not greater than the least prime factor of $m.$
To see the necessity, note that if $p|m$ then the representing polynomial $F \in \mathbb{Z}[x]$ for the function $f$ will satisfy $F(0)\equiv F(p) \pmod p$ so those values cannot be chosen independently.
For the sufficiency, since $n$ is not greater than the least prime factor of $m$ one has $(i-1,j)=1,$ for any $i\neq j$ and $i,j\in \{0,1,\ldots,n-1\}.$ Thus $i-j$ is a unit in $\mathbb{Z}_m.$ Let $(i-j)^{-1} \in \mathbb{Z}_m$ be denoted by $c_{ij}.$
If $f:\mathbb{Z}_n \rightarrow \mathbb{Z}_m$ is given by $f(i)=b_i,$ for $i=0,1,\ldots,n-1$ the following expression
$$
F(x)=\sum_{i=0}^{n-1}b_i \prod_{\stackrel{j=0}{j\neq i}}^{n-1} c_{ij}(x-j)
$$
will represent the function $f.$
A: 
If $F:\Bbb Z/n\Bbb Z\to \Bbb Z/n\Bbb Z$ is given by a polynomial then for each $m \mid n$, $F(a)\equiv F(a+m)\bmod m$.  Not all functions satisfy this condition.

If $n$ is squarefree and $F$ satisfies this condition then it is given by a polynomial: let $n=\prod_j p_j$, $c_j \frac{n}{p_j} \equiv 1\bmod p_j$, we'll have $$F(x) =\sum_j c_j \frac{n}{p_j^{e_j}} \sum_{a=0}^{p_j-1} F(a)(1-(x-a)^{p_j-1}).$$
I don't know if there is a simple congruence condition ensuring that $F$ is given by a polynomial when $n$ is not squarefree.
A: Suppose you have a composite $n=ab$, with $a,b>1$. Any function that satisfies $f(0)=0, f(a)=1$ can not be a polynomial otherwise we would have
$$0=b\left(f(a)-f(0)\right)=b$$
in $\mathbb Z/n\mathbb Z$, which is a contradiction. However this is not a problem for $n$ prime, where you can use Lagrange interpolation to represent any function as a polynomial.
