If n+1 is a cube show that 504 divides n(n+1)(n+2)

Question

If $n+1$ is a cube show that 504 divides $n(n+1)(n+2)..$ I try that : $n+1=a^3$ , then $n=a^3-1$ so $n(n+1)(n+2) = (a^3-1)a^3(a^3+1) = (a^6-1)a^3$ and I try prove $(a^6-1)a^3$ divides by 504 with induction but it is not easy (or short). I just find anybody who solve this problem nice and short. And it is so important for me.. Please help me ...

Answer 1

Hint $\ 504 = 7\cdot 8\cdot 9.\,$ Use little Fermat and CRT to show $\,(\color{#0a0}{a^6\!-\!1})\color{#c00}{a^3}=\color{blue}{a^9\!-\!a^3}\equiv 0$ mod $\,7,8,9$

$\qquad\qquad{\rm mod}\ 7\!:\,\ a^7\equiv a\,\overset{\times\, a^2}\Rightarrow\, \color{blue}{a^9\equiv a^3}$

$\qquad\qquad{\rm mod}\ 8\!:\,\ 2\mid a\,\Rightarrow\, 8\mid \color{#c00}{a^3},\,$ else $\,a^2\equiv 1\,\overset{\rm cube}\Rightarrow \color{#0a0}{a^6\equiv 1}$

$\qquad\qquad{\rm mod}\ 9\!:\,\ 3\mid a\,\Rightarrow\, 9\mid \color{#c00}{a^3},\,$ else $\,\color{#0a0}{a^6\equiv 1}\ $ by $\,\phi(9) = 6\,$ and the Euler-Fermat theorem.

Remark $\ $ The above method easily generalizes to the following, for primes $\,p\ne q$

Theorem $\ \ \ n^{\large k+\phi}\equiv n^{\large k}\pmod{p^i q^j}\ \ $ assuming that $ \ \color{#0a0}{\phi(p^i),\phi(q^j)\mid \phi},\, $ $\, i,j \le k,\,\ p\ne q.\ \ \ $

Proof $\ \ p\nmid n\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^{ \phi}\equiv 1\,\Rightarrow\, n^{k + \phi}\equiv n^k,\, $ by $\ n^{\Large \color{#0a0}\phi} = (n^{\color{#0a0}{\Large \phi(p^{ i})}})^{\large \color{#0a0}m}\overset{\color{blue}{\rm (E)}}\equiv 1^{\large m}\equiv 1\,$ by Euler $\!\rm\color{blue}{(E)}$.

$\qquad\quad\ \ \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^k\equiv 0\,\equiv\, n^{k + \phi}\ $ by $\ n^k = n^{k-i} \color{#c00}n^i = n^{k-i} (\color{#c00}{mp})^i$ and $\,k\ge i.$

So $\ p^i\mid n^{k+\phi}\!-n^k.\,$ By symmetry $\,q^j$ divides it too, so their lcm $ = p^iq^j\,$ divides it too. $\ $ QED

Remark $\ $ Obviously the proof immediately extends to an arbitrary number of primes. This leads the way to Carmichael's Lambda function, a generalization of Euler's phi function.

Answer 2

You need to show that $(a^3-1)a^3(a^3+1)$ is divisible by $9$, $8$, and $7$ (since $504=9\cdot8\cdot7$). Your idea of rewriting the product at $(a^6-1)a^3$ is a good one, since that takes care of $7$, using Fermat's little theorem.

For the other two, you can factor the product at $k^3(k-1)(k+1)(k^2+k+1)(k^2-k+1)$. For divisibility by $8$, you either have $k$ is even, which gives $8\mid k^3$, or $k-1$ and $k+1$ are both even, in which case one of them is divisible by $4$ and the other by $2$. Likewise, you either have $27\mid k^3$, or you have one of $k-1$ and $k+1$ divisible by $3$ and one of $k^2+k+1$ and $k^2-k+1$ divisible by $3$.