### Abstract

A function f: ℤ_{n} → ℤ_{m} is said to be congruence preserving if for all d dividing m and a,b ∈ {0, 1,...,n - 1}, a ≡ b (mod d) implies f(a) = f(b) (mod d). In previous work, Chen defines the notion of a polynomial function from ℤ_{n} to ℤ_{m} and shows that any such function must also be a congruence preserving function. Chen then raises the question as to when the converse is true, i.e. for what pairs (n,m) is a congruence preserving function f : ℤ_{n} → ℤ_{m} necessarily a polynomial function? In the present paper, we give a complete answer to Chen's question by determining all such pairs. We also show that 7/π^{2} is the natural density in ℕ of the set of all m such that the polynomial functions from ℤ_{m} to itself are precisely the congruence preserving functions from ℤ_{m} to itself. Moreover, we obtain a formula for the number of congruence preserving functions from ℤ_{n} to ℤ_{m}.

Original language | English (US) |
---|---|

Pages (from-to) | 15-21 |

Number of pages | 7 |

Journal | Discrete Mathematics |

Volume | 173 |

Issue number | 1-3 |

DOIs | |

State | Published - Aug 20 1997 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics