# polynomials and functions on $\mathbb{Z}/n\mathbb{Z}$

My general question is How is the set of all polynomial functions on $\mathbb{Z}/n\mathbb{Z}$ structured?

What is the number of such functions?

How, given a function, one can recognize that it is polynomial and find a polynomial?

How this set is structured as a $\mathbb{Z}/n\mathbb{Z}$ module ?

(By polynomial function I mean a polynomial considered as a function $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ i.e. polynomials are considered equal iff their values at every point are equal)

• What you are referring to are polynomial functions rather than polynomial. When $n$ is prime, then every function is a polynomial function (by Gaussian interpolation), though this is clearly not true otherwise (for example you can't have $f(0)=0$ and $f(2)=1$ for $n=4$). – tomasz Jan 20 '14 at 15:54
• Yes, I actually called them polynomial functions :) Yes the prime case is easy, but I don't know what to do even in the ring $\mathbb{Z}/p^2\mathbb{Z}$ for prime $p$. Of course it is easy to bound the number of functions by the Euler theorem, but that is not enough (because this module has elements with torsion $p$ that are not dividible by $p$) – user68061 Jan 20 '14 at 16:03
• I don't have an answer, but you should certainly start by looking at the prime-power case (to which hopefully the Chinese remainder theorem would reduce the general case). For the case $n=p^r$, a necessary condition on $f$ is that if $x\equiv y\pmod{p^i}$ for some $i$ then $f(x)\equiv f(y)\pmod{p^i}$. To prove that this is sufficient, in the case $r=2$, it would be enough to construct $f$ such that $f(0)=p$ and $f(i)=0$ for all other $i$. I didn't think about this too hard, but I suspect using $\mathbb{Z}_p$ as base ring and considering the structure of its group of units would be fruitful. – Gro-Tsen Jan 20 '14 at 16:33
• Actually, it turns out that there is an answer here. Apparently the necessary condition I gave is not sufficient, and the paper by Carlitz "Functions and polynomials (mod $p^n$)" (Acta Arith. 9 (1964) 67–78) gives a necessary and sufficient condition. The case of several prime factors is not difficult. – Gro-Tsen Jan 20 '14 at 16:48