Roots in $\mathbb{Z}_m$

Solution 1:

Hint $\ $ Note that $\ 2,3\mid f(n) = n^3\!-n = (n\!-\!1)n(n\!+\!1)\ $ for all $\,n,\,$ so $\,6\mid f(n)\,$ for all $\,n\,$ i.e. $\,f(x) = \,x^3\!-x = 0\,$ as a function on $\,\Bbb Z_6.$ Using $\,x^3\! = x\,$ as a rewrite rule we can reduce all powers of $\,x\,$ to powers $\le 2,\,$ so any polynomial function is equal to a polynomial function of degree $\le 2.\,$ However, these reduced polynomials are not all distinct functions, e.g. note that $\ 3x^2 = 3x\ $ since their difference $\,3x(x\!-\!1)\, $ is the zero function on $\,\Bbb Z_6,\,$ since $\,2\mid n(n\!-\!1).\,$

Remark $\ $ One can generalize the above analysis to obtain an axiomatization of the identities satsified by any fixed list of finite fields - see the following, excerpted from Stanley Burris and John Lawrence, Term rewrite rules for finite fields (1991). For example, the Lemma below implies that any polynomial identity that holds true in $\,\Bbb F_4,\,\Bbb F_9,\,\Bbb F_{25}\,$ is an equational consequence of

$$\begin{eqnarray} 30 = 0,\ \ & 15(x^4-x) = 0\\ x^{25}\! = x,\ \ & 10(x^9-x) = 0\\ & \ 6(x^{25}-x) = 0\end{eqnarray}$$

Solution 2:

I had a reason to dig up the history of this problem once. A solution was published by Singmaster in the 1960s and by Niven & Warren in the late 50s. Even earlier Carlitz studied necessary and sufficient criteria for a function from $\Bbb{Z}_m$ to itself to come from a polynomial with integer coefficients. He claimed that a description of the set $S_m$ was a guided exercise in Dickson's textbook from 1910s. I haven't checked but I have no reason to suspect that. So this problem has been solved and forgotten periodically.

A quick summary.The set $S_m$ is clearly an ideal in $\Bbb{Z}_m[x]$. Chinese remainder theorem is your friend, and allows you to reduce the problem to the case where $m$ is a power of a prime number. Bill's answer (+1) is on the money in the sense that descending factorials are the key. After all $$ r_k(x):=x(x-1)(x-2)\cdots (x-k+1)=k!\binom{x}{k} $$ manifestly vanishes modulo $k!$.

Here's how we use that. As an example let's do $m=2^{10}$. The following polynomials belong to the ideal $S_m$ and generate it (not trivial, but not exceedingly hard either - search for those papers for the details):

• the values of $r_2(x)$ are all even, so $2^9r_2(x)\in S_{1024}$,
• the values of $r_4(x)$ are all divisible by $4!$, hence by $8$, so $2^7r_4(x)\in S_{1024}$,
• the values of $r_6(x)$ are all divisible by $6!$, hence by $2^4$, so $2^6r_6(x)\in S_{1024}$,
• the values of $r_8(x)$ are all divisible by $8!$, hence by $2^7$, so $2^3r_8(x)\in S_{1024}$,
• similarly we see that $2^2r_{10}(x)\in S_{1024}$,
• and finally we see that as $2^{10}\mid 12!$, the values of $r_{12}(x)$ are all divisible by $2^{10}$. Thus the MONIC polynomial $r_{12}(x)\in S_{1024}$, and therefore in the quotient ring $\Bbb{Z}_{1024}[x]/S_{1024}$ all the cosets have a representative of degree $<12$.

Similarly with other primes $p$, we can use the polynomials $r_{jp}(x)$ and need to figure out (that is easy) the exact power of $p$ that divides $(jp)!$.