Олимпиада Туймаада по математике. Старшая лига. 2018 год

Дано натуральное число $n$ и простое число $p$. Оказалось, что произведение $(1^3+1)(2^3+1)\ldots ((n-1)^3+1)(n^3+1)$ делится на $p^3$. Докажите, что $p\leq n+1$. ( Z. Luria )

Комментарий/решение

От противного $p>n+1$

Тогда все числа от $1$ до $n+1$ взаимопростые с $p$. Значит если немного перепишем условия то $$p^3 \mid (1^2-1+1)(2^2-2+1) \dots ((n-1)^2-(n-1)+1)(n^2-n+1)$$

Теперь поймем, что если одна из этих скобок поделится на p, то уже никакая другая из них не будет делится на р. Докажем это.

От противного

$(n-k)^2-(n-k)+1 \equiv (n-m)^2-(n-m)+1 \equiv 0 \pmod p$

Очевидно что $n-1 \geq k;m \geq 0$ и $k≠m$

Тогда из $(n-k)^2-(n-k)+1 \equiv (n-m)^2-(n-m)+1$ следует, что $(k-m)(2n-1-k-m) \equiv 0 \pmod p$ (раскройте скобки, сократите все что можно а потом сново попробуйте как то по скобкам раскидать)

Тогда либо $k \equiv m \pmod p$ но $p>n>k;m$ и $k≠m$ значит это невозможно

Либо $(2n-1-k-m) \equiv 0 \pmod p$ т.е. $2n \equiv k+m+1 \leq n-1+n-1+1=2n-1 \pmod p$ Противоречие

Значит максимум только одна скобка может поделится на р, но наибольшая из скобок будет $n^2-n+1$ но $p^3>(n+1)^3>n^2+1>n^2-n+1>0$ от чего $p^3 \nmid n^2-n+1$

Значит если вдруг $p>n+1$ то условие с делимостью не выполняется поэтому $p \leq n+1$