Polynomials that induce the zero function mod $n$ 
*

*Which polynomials induce the zero function mod $n$?


In particular:


*

*What is the polynomial of least degree that induces the zero function mod $n$?

*What is the monic polynomial of least degree that induces the zero function mod $n$?
These are not vacuous questions because of the following general result:

If $r$ is the maximum exponent in the prime factorization of $n$, then $x \mapsto x^{r+\lambda (n)}-x^r$ is the zero function mod $n$. [Wikipedia]

Here, $\lambda$ is the Carmichael function.


*

*When is $x^{r+\lambda (n)}-x^r$ the monic polynomial of least degree that induces the zero function mod $n$?


Fermat's theorem implies that $x^n-x$ is the answer for $n$ prime: all polynomials that induce the zero function mod $n$ are a multiple of $x^n-x$.
How can this be generalized to composite $n$?
Here are some other examples:
$$
\begin{array}{rll}
n & L_n: \text{least degree} & M_n: \text{least degree monic}
\\ 2 & x^2+x
\\ 3 & x^3-x
\\ 4 & 2(x^2+x) & x^4-x^2
\\ 5 & x^5-x
\\ 6 & 3(x^2+x) & x^3-x
\\ 7 & x^7-x
\\ 8 & 4(x^2+x) & x^4+2x^3+3x^2+2x = x(x+1)(x^2+x+2)
\\ 9 & 3(x^3-x) & x^8-x \quad (???)
\\ 10 & 5(x^2+x) & x^5-x
\\ 11 & x^{11}-x
\\ 12 & 6(x^2+x) & x^4+5x^2+6x = x(x+1)(x^2-x+6)
\\ 13 & x^{13}-x
\\ 14 & 7(x^2+x) & ???
\\ 15 & 5(x^3-x) & x^5-x
\\ 21 & 7(x^3-x) & ???
\\ 24 & 12(x^2+x) & x^4+2x^3+11x^2+10x = x(x+1)(x^2+x+10)
\end{array}
$$
It seems clear that $L_{2m}=m(x^2+x)$, because $x^2+x$ is always even.
More generally,


*

*Is $L_{pq} = qL_p$ and $M_{pq}=L_q$ for $p<q$ primes?

*If $n=pm$ and $p$ is smallest prime divisor of $n$, then is $L_{pm}=mL_p$?
Corrections and additions welcome.
Please collect partial results as answers.
 A: Edited and improved
Using the fact that the product of any $n$ consecutive integers is divisible by $n!$ we immediately get
Lemma 1 Let $R_n(X)=X(X-1)(X-2)...(X-n+1)$. Then $R(X)$ is trivial $\pmod{n!}$.  
Lemma2: Let $P(X)=a_kX^k+..+a_1X+a_0$ and let $p$ be prime. If $P(X)$ is trivial modulo $p$ and $p$ does not divide all coefficients of $P(X)$ then $k \geq p$.
Proof: Since $P(X)$ has $p$ roots in the field $\ZZ_p$, it has degree at least $p$ modulo $p$. Then $k \geq p$.

As consequences we get immediately:
Lemma 3: If $p$ is prime, and $n$ is so that $p|n$ and $n |p!$ then 
$$
M_n=X(X-1)(X_2)...(X-p+1)=: R_p
$$
[Or another polynomial of same degree, namely $M_n=R_p+Q(X)L_n(X)$ for some $Q(X)$.]
Proof: Since $n|p!$, by Lemma 1 $R_p(X) $ is trivial modulo $n$. By Lemma2, $deg(M_n) \geq p$.
\qed
Lemma 4 If $p$ is the smallest prime dividing $n$, and $n$ is square free, then 
$$L_n=\frac{n}{p}(X^p-X)$$
Proof It is clear that this polynomial works. We show next $\deg(L_n) \geq p$.
Let $L_n=a_kX^k+....a_1X+a_0$. Take the first coefficient $a_l$ which is not divisible by $n$. Then, there exists a prime $q|n$ such that $q \nmid a_l$.
By Lemma 2$deg(L_n) \geq q \geq p$.
Final Note: Your $M_8$ is wrong. Note that if $n$ is even then $8|n(n-2)$ and if $n$ is odd $8|(n-1)(n+1)$.
I think that it is easy to show that $M_8=(X-2)(X-1)X(X+1)$ or something equivalent $\pmod{8}$. THis also works for $M_{24}$.
A: Not complete answers, but too large for comment. I have the results, when $n=p_1^{\alpha_1}\cdots p_{k}^{\alpha_k}$:

Non-monic case: The minimal degree is exactly $\min p_i.$
Monic case: The minimal degree is the maximum of the degrees for each $p_i^{\alpha_i}.$ The degree of $p_i^{\alpha_i}$ must be divisible by $p_i$ and is at most $\alpha_ip_i.$ This is not the absolute minimum, for example when $p=2$ and $\alpha=3,$ the minimal degree for $8$ is $4<6=p\alpha.$
My conjecture is that the minimal monic degree $d$ for $p^k$ is the smallest $d$ such that $\nu_p(d!)\geq k.$
If that is true, then if $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ then the minimal monic degree is the minimal $d$ such that each $p_i^{\alpha_i}$ divides $d!.$

Non-monic case:
If $d(n)$ is the smallest degree for $n$ in the non-monic case, we can get, for any $m.n,$ $d(mn)=\min(d(m),d(n)).$
This is because if $p_m(x)$ is a minimal polynomial for $m$ then we take $np_m(x).$
This means that if $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots$ then $d(n)=\min_i d\left(p_i\right).$ But when $p$ is prime, $d(p)=p,$ so we get $d(n)=\min_i p_i.$
Monic case:
If $D(n)$ is the smallest degree of a monic, then when $\gcd(m,n)=1$ you have that $D(mn)=\max (D(m),D(n)).$
This is because if $p_m,p_n$ are the corresponding monic polynomials with $D(m)\geq D(n)$ you can apply Chinese remainder theorem coefficient by coefficient to find a polynomial $P_{mn}$ so that:
$$\begin{align}P_{mn}(x)&\equiv p_m(x)\pmod{m}\\
P_{mn}(x)&\equiv x^{D(m)-D(n)}p_n(x)\pmod{n}\end{align}$$
Since both polynomials are monic and of degree equal to the $D(m),$ we get $P_{mn}$ monic and $P_{mn}(x)$ satisfies your conditions.
We also have that $D\left(p^{\alpha}\right)\leq p\alpha$ since $(x^p-x)^{\alpha}$ is monic of degree $p\alpha$ and satisfies our conditions.

As noted in my comments above, if $p(x)$ is always zero modulo $n$ then so is $p(x+1)-p(x).$
In the monic case, this means if $p(x)$ is minimal then $d=\deg p(x)$ must have a common factor with $n,$ since otherwise $q(x)=p(x+1)-p(x)$ is of smaller degree with leading coefficient $d$ so we solve $du-nv=1$ and take $r(x)=uq(x)-nvx^{d-1}$ which is monic of smaller degree and satisfies our condition.

To finish the question, one needs to compute a value of $D(p^{\alpha}),$ which we know is divisible by $p$ and $\leq p\alpha.$

Conjecture
My guess is that $D\left(p^{\alpha}\right)$ is the smallest $d$ such that $\nu_p(d!)\geq \alpha.$ In particular, if $\alpha\leq p$ then $d=\alpha p.$
If $\alpha=p+1$ then $\nu_p\left((p^2)!\right)=p+1.$ Do $D(p^p)=D(p^{p+1})=p^2.$
This is definitely an upper bound, because the falling factorial $(x)_d$ is monic and of degree $d$ and is always divisible by $p^{\nu_p(d)}.$
A: These papers characterize the polynomials that induce the zero function mod $n$:

*

*On polynomial functions (mod $n$) by Singmaster (1974)


*Polynomials and their residue systems by Kempner (1921)
Kempner's paper is closer to what I have in mind. I'll have to check it more closely.
I came across Kempner's paper in the paper A basis for residual polynomials in $n$ variables by Litzinger (1935).
