Largest modulus for Fermat-type polynomial
Motivated by this question, I wonder:
Given $k\in\mathbb N, k\ge2$, what is the largest $m\in\mathbb N$ such that $n^k - n$ is divisible by $m$ for all $n\in\mathbb Z$ ?
To find the highest power of a prime $p$ dividing $m$, we find the highest $r$ such that $n\mapsto n^k-n$ is identical to the zero map on $\Bbb Z/p^r\Bbb Z$. If $r>1$ then $p^k\equiv p~(p^r)$, which is impossible, so $r\in\{0,1\}$.
Therefore it suffices to find primes $p$ such that $n^k\equiv n$ on all of $\Bbb Z/p\Bbb Z$. This occurs if and only if
$$(p-1)\mid(k-1),$$
because $(\Bbb Z/p\Bbb Z)^\times$ is cyclic. Hence $m$ is the product of all primes $p$ such that $(p-1)|(k-1)$.
The answer is in my post in the question you linked: it follows immediately from the following global Euler-Fermat theorem, excerpted from my 2009/04/10 sci.math post.
Theorem $\ $ For natural numbers $\rm\:a,e,n\:$ with $\rm\:e,n>1$
$\qquad\rm n\:|\:a^e-a\:$ for all $\rm\:a\:\iff n\:$ is squarefree, and prime $\rm\:p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e\!-\!1$
Proof $\ (\Leftarrow)\ $ Since a squarefree natural divides another iff all its prime factors do, we need only show $\rm\:p\:|\:a^e\!-\!a\:$ for each prime $\rm\:p\:|\:n,\:$ or, that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1} \equiv 1\pmod p,\:$ which, since $\rm\:p\!-\!1|\:e\!-\!1,\:$ follows from $\rm\:a \not\equiv 0\:$ $\Rightarrow$ $\rm\: a^{p-1} \equiv 1 \pmod p,\:$ by little Fermat.
$(\Rightarrow)\ $ Given that $\rm\:n\:|\:a^e\!-a\:$ for all naturals a we must show
$\rm\qquad(1)\ \ n\:$ is squarefree, and $\rm\ \ (2)\ \ p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e\!-\!1.$
$\rm(1)\ \ $ Nonsquarefree $\rm\:n\:$ has a divisor $\rm\:a^2\ne 1\:$ so $\rm\: a^2\:|\:n\:|\:a^e\!-\!a\:$ $\Rightarrow$ $\rm\:a^2\:|\:a\:$ $\Rightarrow\Leftarrow$ $\rm\: (e>1\:$ $\Rightarrow$ $\rm\: a^2\:|\:a^e)$
$\rm(2)\ \ $ Let $\rm\:a\:$ be a generator of the multiplicative group of $\rm\:\mathbb Z/p.$ Thus $\rm\:a\:$ has order $\rm\:p\!-\!1.\:$ Now $\rm\:p\:|\:n\:|\:a\,(a^{e-1}\!-1)\:$ but $\rm\:p\nmid a,\:$ so $\rm\: a^{e-1}\! \equiv 1 \pmod p,\:$ thus $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ the order of $\rm\:a\ mod\ p.\ \ $ QED
See said sci.math post for more. Note: to fix rotted Google Groups links in the cited sci.math post it may be necessary to change $\ $ http://google.com/... $\ $ to$\ $ http://groups.google.com/... i.e. insert "groups." before "google.com".