Characterizing congruence preserving functions \(\mathbb Z/n\mathbb Z \to \mathbb Z/m\mathbb Z\) via rational polynomials (Q2830401)

A function \(f:\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\) is said to be \textit{congruence preserving} if, for every \(d\mid m\) it holds that NEWLINE\[NEWLINEa\equiv b\pmod{d} \Rightarrow f(a)\equiv f(b)\pmod{d}.NEWLINE\]NEWLINE The authors first show that the set of functions \(\{P_0,P_1,\dots,P_{n-1}\}\), with \(P_k:\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\) defined by \(P_k(x)=\binom{x}{k}\) is a basis of the \((\mathbb{Z}/m\mathbb{Z})\)-module of functions \(\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\).NEWLINENEWLINEThen, the main result of the paper states that a function \(f:\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\) is congruence preserving if and only if \(f=\sum_{i=0}^{n-1} a_iP_i\) with \(a_i\) a multiple of \(\mathrm{lcm}(i)\) in \(\mathbb{Z}/m\mathbb{Z}\).NEWLINENEWLINEFinally, the authors use this result in order to count the number of counting preserving functions \(\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\) in terms of the prime-power decomposition of \(m\).