Characterizing congruence preserving functions $Z/nZ\to Z/mZ$ via rational polynomials

Abstract

We introduce a basis of rational polynomial-like functions $P_0,\dots ,P_{n-1}$ for the free module of functions $Z/nZ\to Z/mZ$. We then characterize the subfamily of congruence preserving functions as the set of linear combinations of the functions $lcm(k)P_k$ where $lcm(k)$ is the least common multiple of $2,\dots ,k$ (viewed in $Z/mZ$). As a consequence, when $n\ge m$, the number of such functions is independent of $n$.