Condition of cube of prime dividing $\prod_{i = 0}^{n} ((n - i)^3 + 1)$

Question

This is a question from a French high school maths competition that I participated in today:

Let $n$ be a positive integer. Let $p$ be a prime number such that $$p^3 \text{ divides } (1^3 + 1)(2^3 + 1)\cdots\left((n-1)^3 + 1\right)(n^3 + 1).$$ Show that $p \leq n + 1$.

I have approached it by writing each $(n - i)^3 + 1$ in $\prod_{i = 0}^{n}\left((n - i)^3 + 1\right)$ as $(n - i + 1)\left((n - i)^2 - (n - i) + 1\right)$, and then the product then becomes $$\begin{aligned} &\prod_{i = 0}^n (n - i + 1)\left((n - i)^2 - (n - i) + 1\right)\\ &= (n + 1)! \prod_{i = 0}^n \left((n - i)^2 - (n - i) + 1\right) \end{aligned}$$

If for the sake of contradiction, $p \leq n + 1$ does not hold, then $p$ does not divide $(n + 1)!$ and hence $p^3$ divides $\prod_{i = 0}^n \left((n - i)^2 - (n - i) + 1\right)$. Sadly, I failed to find the contradiction.

My question is then: where is the contradiction? Is there a better approach?

Answer 1

It's easier to write the product as:

$$p^3|\prod_{i=1}^n(i^2-i+1).$$ Now, if $p>n+1$, then $p^2 >(n+1)^2\geq i^2-i+1. $ This means that there must be $1<i<j<k\leq n$ such that $p$ divides each of the factors corresponding to these indices. From this it is easy to get a contradiction. If $$p|i^2-i+1,\,\, j^2-j+1 $$ then their difference is also divisible by $p:$ $$p|(i-j)(i+j-1).$$ This also implies $$p|i+j-1.$$ Now do the same for the remaining possibilities and get a contradiction.

Answer 2

In fact, it holds that $p\leq n-1$ (the inequality becomes an equality if and only if $p=2$ and $n=3$). Suppose on the contrary that $p\geq n$. The case $p=n$ can be reduced to the case $p=n+1$ by noting that $p^3+1$ is not divisible by $p$, and so the factor $p^3+1$ is irrelevant. We can now safely assume that $p>n$.

As you say, we have $$p^3\mid \prod_{k=0}^n\,(k^2-k+1)\,.$$ Observe the followings. First, $p^2$ does not divide $k^2-k+1$ for any $$k\in\{0,1,2,\ldots,n\}\subseteq \{0,1,2,\ldots,p-1\}\,.$$ This is simply because $$0<k^2-k+1\leq k^2\leq (p-1)^2<p^2\,.$$ Hence, if $p^3\mid \prod\limits_{k=0}^n\,(k^2-k+1)$, then there must exist three pairwise distinct values $$k_1,k_2,k_3\in\{0,1,2,\ldots,n\}\subseteq \{0,1,2,\ldots,p-1\}$$ such that the congruence $t^2-t+1\equiv0\pmod{p}$ has solutions $t=k_1$, $t=k_2$, and $t=k_3$. However, since $\mathbb{Z}/p\mathbb{Z}$ is a field, any quadratic polynomial in $(\mathbb{Z}/p\mathbb{Z})[t]$ has at most two solutions modulo $p$, and this is a contradiction you are looking for.