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

I am studying polynomial congruences, and there is a result that states that for any function $F: \mathbb{Z}/p\mathbb{Z}\rightarrow \mathbb{Z}/p\mathbb{Z}$ (where $p$ is prime), there is a polynomial $f(x)$ with integral coefficients and degree at most $p-1$, or $f(x)=0$, such that $F(x)\equiv f(x)\mod p$ for all $x\in \mathbb{Z}/p\mathbb{Z}$. A straight-forward approach to this is constructive; we let $$f(x)=\sum_{i=1}^{p}{F(i)(1-(x-i)^{p-1})}$$ which clearly has the desired properties.

I am supposed to show that if we replaced $p$ with $m$, where $m$ is a composite integer, this is false.

My attempts at this proof have been attempts at a constructive proof; namely showing that for every composite $m$ we can construct some function $G: \mathbb{Z}/m\mathbb{Z}\rightarrow \mathbb{Z}/m\mathbb{Z}$ that cannot be represented by a polynomial $g(x)$ with integral coefficients and degree at most $m-1$, or $g(x)=0$, such that $G(x)\equiv g(x)\mod m$. I have also been attempting to use the fact that this function can clearly map between zero divisors, or $x$ such that $(x,m)\neq 1$, to try and derive a contradiction if such a polynomial $g$ does indeed exist. With neither of these approaches have I gotten very far.

Thank you in advance.

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

If $m$ is composite and $d$ is a proper divisor of $m$ ($d>0$, $d\notin\{1,m\}$), then set $G(0)=0$, $G(d)=1$. Since $G(0)=0$, any polynomial $g(x)$ representing $G(x)$ would have to have constant term divisible by $m$. However, then $d\mid g(d)$, so $G(d)\not\equiv g(d)\ \pmod m$. Therefore $G(x)$ is not representable by any polynomial with integer coefficients.

share|cite|improve this answer

This is a large hint towards the solution for general composite $m$. Let $m=6$. Consider the function which is $0$ at $0$ and $1$ at $2$, and whatever you like elsewhere.

share|cite|improve this answer

If $I$ is an ideal of a ring $R$, any polynomial (over $R$) function $R\to R$ always induces a polynomial function $R/I\to R/I$ by reducing the coefficients of a representing polynomial modulo $I$. But for a general function $f:R\to R$ to induce a function $R/I\to R/I$, it is necesssary that $f$ maps each class modulo $I$ into a single class modulo $I$; whenever $I$ is a nonzero proper ideal there are certainly some functions that violate this. Such functions cannot be polynomial functions.

Now use that $R=\mathbf Z/n\mathbf Z$ has nonzero proper ideals if (and only if) $n$ is composite.

The multiples of a divisor $d\notin\{1,n\}$ of $n$ will provide such an ideal$~I$. To make a concrete function $f:R\to R$ that is not polynomial, it suffices to take two elements in the same class modulo $I$, for instance $0$ and $d$, and have $f$ map them to elements of distinct classes modulo $I$, for instance $0$ and $1$. You can find this example in other answers, and a detailed expansion of the above argument of why it cannot be polynomial.

share|cite|improve this answer

$\rm\begin{eqnarray}{\bf Hint} &&\rm n \equiv g(0),\ g(n) \equiv 1\,\ (mod\ nk)\\ \Rightarrow &&\rm 0 \equiv g(0),\ g(0)\equiv 1\,\ (mod\ n)\end{eqnarray}$

share|cite|improve this answer

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.