# 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$ ?

• Is there a better name for the polynomials $x^k-x$? – lhf Jun 29 '12 at 12:05

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

• Of course! Thanks. – lhf Jun 29 '12 at 11:40

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".

• Sorry, missed that. Thanks. – lhf Jun 29 '12 at 15:11