Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Which functions satisfy $\forall n,x,y (x \equiv y \pmod n \implies f(x) \equiv f(y) \pmod n )$ ?

I know polynomials do; are there others?

share|cite|improve this question
up vote 3 down vote accepted

There are such functions which are not polynomials. We will construct an example of a function $g$ which grows faster than any polynomial, and such that for all integers $m \ge 1$, and all non-negative integers $x$ and $y$, if $x \equiv y \pmod{m}$, then $g(x)\equiv g(y)\pmod{m}$. It will follow immediately that if $f(x)=g(x^2)$, then for all integers $x$, $y$, if $x \equiv y \pmod{m}$ then $f(x) \equiv f(y)\pmod{m}$, and $f$ is not a polynomial.

Let $g(0)=1$. Suppose that we have defined $g(k)$ for all non-negative $k<n$. We show how to define $g(n)$. It is easy to find a polynomial $P_n(x)$, with integer coefficients, such that $P_n(k)=g(k)$ for all integers $k$ with $0 \le k <n$. Let $g(n)= P_n(n)+(A_n)(n!)$, where $A_n$ is chosen so that (say) $g(n)>2^n$ (this part is to make sure that $g$ grows faster than any polynomial).

Suppose that $g$ has the desired congruence property for all $x$, $y$ with $0 \le x, y <n$. We show it has the desired congruence property for $0 \le x, y \le n$. Let $0 \le x <n$. If $m$ is positive and $x \equiv n \pmod{m}$, then $m \le n$, so $g(n) \equiv P_n(n) \pmod{m}$. But $P_n(x)\equiv P_n(n)\pmod{m}$, since $P_n$ is a polynomial.

share|cite|improve this answer
I haven't checked the details, but I suspect what you are doing is diagonalizing out of polynomials. This was in fact the genesis of the diagonalization method, viz. du Bois-Reymond discovered the method for the purpose of diagonalizing on asymptotic growth rates (order of infinity). Only later was it (independently?) discovered by Cantor. – Bill Dubuque Mar 29 '11 at 16:39
Sort of, I guess. By choosing the $A_n$ appropriately, one can make the values of the function positive or negative in any pattern. So there are continuum many functions that satisfy the condition. Too bad, it would have been nice if there were \emph{some} structure. – André Nicolas Mar 29 '11 at 19:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.