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.

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)}.$
