6
$\begingroup$

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?

1 Answers 1

3

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. 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 . 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 . We show it has the desired congruence property for $0 \le x, y \le n$. Let $0 \le x . 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.

  • 1
    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.2011-03-29