Intereting Posts

Probability of winning a prize in a raffle
How were Hyperbolic functions derived/discovered?
Shortest way of proving that the Galois conjugate of a character is still a character
A formula for n-derivative of the inverse of a function?
Calculating in closed form $\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{1}{m^4(m^2+n^2)}$
Intuitively, why is the Euler-Mascheroni constant near sqrt(1/3)?
Use Little Fermat Theorem to prove $341$ is not a prime base $7$
Evaluate the integral $\int_{0}^{\infty} \frac{1}{(1+x^2)\cosh{(ax)}}dx$
What are some examples of theories stronger than Presburger Arithmetic but weaker than Peano Arithmetic?
Is every compact space compactly generated?
How to go from local to global isometry
Cyclic modules over a polynomial ring
Transpose map in $M(2,\mathbb{R})$
Does $M_n^{-1}$ converge for a series of growing matrices $M_n$?
Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$

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

- Proof about fibonacci numbers by induction
- cannot be the value of the expression.
- A number-theory question on the deficiency function $2x - \sigma(x)$
- Is it possible to describe the Collatz function in one formula?
- $x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$
- Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

- Accuracy of Fermat's Little Theorem?
- Prove that if c is a common divisor of a and b then c divides the gcd of a and b..
- Prove that if $7^n-3^n$ is divisible by $n>1$, then $n$ must be even.
- What is the sum of the prime numbers up to a prime number $n$?
- $n^5-n$ is divisible by $10$?
- How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?
- Prove every odd integer is the difference of two squares
- $\sqrt{13a^2+b^2}$ and $\sqrt{a^2+13b^2}$ cannot be simultaneously rational
- Prove by contradiction that every integer greater than 11 is a sum of two composite numbers
- Why is $(2+\sqrt{3})^{50}$ so close to an integer?

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

- What is the support of a localised module?
- When is $2^n \pm 1$ a perfect power
- Is $\sum\limits_{n=1}^{\infty}\frac{n!}{n^n}$ convergent?
- Remark 3.1.3 from Introduction to Representation Theory from Pavel Etingof
- Constructing a subset of an uncountable set which is neither countable nor co-countable
- How can I pick up analysis quickly?
- $f$ is irreducible $\iff$ $G$ act transitively on the roots
- Does Lowenheim-Skolem theorem depend on axiom of choice?
- A.P. terms in a Quadratic equation.
- How to prove $\forall Y \subset X \ \forall U \subset X \ (Y \setminus U = Y \cap (X \setminus U))$?
- Generalization of $\lfloor \sqrt n+\sqrt {n+1}+\sqrt{n+2}+\sqrt{n+3}+\sqrt{n+4}\rfloor=\lfloor\sqrt {25n+49}\rfloor$
- Infinite Series $\sum\limits_{k=1}^{\infty}\frac{k^n}{k!}$
- An ideal which is not finitely generated
- $x^5 – y^2 = 4$ has no solution mod $m$
- Why 6 races are not sufficient in the 25 horses, 5 tracks problem