# Representation of functions between residue classes of $\mathbb{Z}/m\mathbb{Z}$ as polynomials

I am studying polynomial congruences, and there is a result that states that for any function $F: \mathbb{Z}/p\mathbb{Z}\rightarrow \mathbb{Z}/p\mathbb{Z}$ (where $p$ is prime), there is a polynomial $f(x)$ with integral coefficients and degree at most $p-1$, or $f(x)=0$, such that $F(x)\equiv f(x)\mod p$ for all $x\in \mathbb{Z}/p\mathbb{Z}$. A straight-forward approach to this is constructive; we let $$f(x)=\sum_{i=1}^{p}{F(i)(1-(x-i)^{p-1})}$$ which clearly has the desired properties.

I am supposed to show that if we replaced $p$ with $m$, where $m$ is a composite integer, this is false.

My attempts at this proof have been attempts at a constructive proof; namely showing that for every composite $m$ we can construct some function $G: \mathbb{Z}/m\mathbb{Z}\rightarrow \mathbb{Z}/m\mathbb{Z}$ that cannot be represented by a polynomial $g(x)$ with integral coefficients and degree at most $m-1$, or $g(x)=0$, such that $G(x)\equiv g(x)\mod m$. I have also been attempting to use the fact that this function can clearly map between zero divisors, or $x$ such that $(x,m)\neq 1$, to try and derive a contradiction if such a polynomial $g$ does indeed exist. With neither of these approaches have I gotten very far.

Thank you in advance.

If $m$ is composite and $d$ is a proper divisor of $m$ ($d>0$, $d\notin\{1,m\}$), then set $G(0)=0$, $G(d)=1$. Since $G(0)=0$, any polynomial $g(x)$ representing $G(x)$ would have to have constant term divisible by $m$. However, then $d\mid g(d)$, so $G(d)\not\equiv g(d)\ \pmod m$. Therefore $G(x)$ is not representable by any polynomial with integer coefficients.
This is a large hint towards the solution for general composite $m$. Let $m=6$. Consider the function which is $0$ at $0$ and $1$ at $2$, and whatever you like elsewhere.
If $I$ is an ideal of a ring $R$, any polynomial (over $R$) function $R\to R$ always induces a polynomial function $R/I\to R/I$ by reducing the coefficients of a representing polynomial modulo $I$. But for a general function $f:R\to R$ to induce a function $R/I\to R/I$, it is necesssary that $f$ maps each class modulo $I$ into a single class modulo $I$; whenever $I$ is a nonzero proper ideal there are certainly some functions that violate this. Such functions cannot be polynomial functions.
Now use that $R=\mathbf Z/n\mathbf Z$ has nonzero proper ideals if (and only if) $n$ is composite.
The multiples of a divisor $d\notin\{1,n\}$ of $n$ will provide such an ideal$~I$. To make a concrete function $f:R\to R$ that is not polynomial, it suffices to take two elements in the same class modulo $I$, for instance $0$ and $d$, and have $f$ map them to elements of distinct classes modulo $I$, for instance $0$ and $1$. You can find this example in other answers, and a detailed expansion of the above argument of why it cannot be polynomial.
$\rm\begin{eqnarray}{\bf Hint} &&\rm n \equiv g(0),\ g(n) \equiv 1\,\ (mod\ nk)\\ \Rightarrow &&\rm 0 \equiv g(0),\ g(0)\equiv 1\,\ (mod\ n)\end{eqnarray}$