<s>[INST] 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.
 [/INST] 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}$.
</s>