3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ See also oeis.org/A027760 $\endgroup$ – lhf Jun 29 '12 at 11:37
  • 1
    $\begingroup$ Is there a better name for the polynomials $x^k-x$? $\endgroup$ – lhf Jun 29 '12 at 12:05
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Of course! Thanks. $\endgroup$ – lhf Jun 29 '12 at 11:40
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.