Exercise 2.7.7 (Theorem 2.28 is false for composite moduli)

Proof. We can translate Theorem 2.28: every function $f:\mathbb{Z}∕\mathit{p\mathbb{Z}}$ to $\mathbb{Z}∕\mathit{p\mathbb{Z}}$ is a polynomial function of degree at most $p-1$.

We show here that this statement is false is $p$ is replaced by a composite number $m$ (and give an alternative proof of Theorem 2.28 if $m=p$ is a prime number.

Let $A$ be the ring $A=\mathbb{Z}∕\mathit{m\mathbb{Z}}$, and write $A_{m-1}[x]$ the additive group of formal polynomials of degree at most $m-1$.

Consider now the evaluation map from $A_{m-1}[x]$ to the additive group $A^A$ of all functions $A\to A$:

which maps a formal polynomial $f$ of degree less that $m$ to the corresponding polynomial function $\tilde{f}:A\to A$. Then $\phi$ is a group homomorphism: let $g(x)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{m-1}{b}_i{x}^i\in A_{m-1}[x]$.

For all $\alpha \in A$,

thus

Note that $|A_{m-1}[x]|=|A^A|=m^m$: there are as many functions from $A$ to $A$ as formal polynomials with coefficients in $A$ of degree at most $m-1$.

We show that $\phi$ is injective (one-to-one) if and only if $m$ is a prime.

• Suppose that $m=p$ is a prime number. Then $f\in \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )$ if for all $\alpha \in A,f(\alpha )=0$. Then $f(x)=x(x-1)\cdots (x-(p-1))q(x)$ for some polynomial $q\in A[x]$ (by Exercise 2.7.4). If $q(x)\ne 0$, then $\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(f)>p-1$, which is false, therefore $q(x)=0$, and so $f(x)=0$. Hence $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )=\{0\}$ and $\phi$ is injective.

  In this case, since $|A_{m-1}[x]|=|A^A|$, $\phi$ is a bijection. This proves that any function $\mathbb{Z}∕\mathit{p\mathbb{Z}}\to \mathbb{Z}∕\mathit{p\mathbb{Z}}$ is a polynomial function of degree at most $p-1$: this is an alternative proof of Theorem 2.28.

• Suppose that $m$ composite. Then $m=\mathit{ab}$, where $1<b\le a<m$. Consider the polynomial

  $$h(x)=\mathit{ax}(x-1)(x-2)\cdots (x-b+1).$$

  If $\alpha \in \mathbb{Z}$, then $b\mid \alpha (\alpha -1)(\alpha -2)\cdots (\alpha -b+1)$ by Theorem 1.21. Therefore $m=\mathit{ab}\mid f(\alpha )$, for every $\alpha \in \mathbb{Z}$, that is

  $$h(\alpha )=\mathit{a\alpha }(\alpha -1)(\alpha -2)\cdots (\alpha -b+1)\equiv 0(\mathit{mod}\mathit{ab}).$$

  Hence its reduced polynomial $\bar{h}\in A[x]$ modulo $m$ satisfies $\bar{h}(\bar{\alpha })=0$ for every $\bar{\alpha }\in \mathbb{Z}∕\mathit{mZ}$, so

  $$\bar{h}\in \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi ).$$

  Moreover the leading term of $\bar{h}$ is ${[a]}_m{x}^b$, where $1<b\le a<m$, thus $\bar{h}\ne 0$. This proves that $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )\ne \{0\}$, thus $\phi$ is not injective. Since $|A_{m-1}[x]|=|A^A|$, $\phi$ is not surjective (onto). This means that some functions $u:A\to A$ are not polynomial functions of degree at most $m-1$.

  The statement of Theorem 2.28 becomes false if we replace the prime number $p$ by a composite number $m$.