3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$\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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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