Олимпиада Туймаада по математике. Старшая лига. 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$

От противного. По условию для некоторого $1 \le m \le n$

$p \mid m^3+1 = (m+1)(m^2-m+1)$. Поскольку $m+1 < p$ по предположению,

то $p \mid m^2-m+1 < (m+1)^2 < p^2$, откуда $v_p(m^2-m+1)=1$.

Тогда по условию найдутся $m,k,l \le n$ такие, что $p$ делит каждую из

$f(x)=x^2-x+1$ при $x=m,k,l$. Но тогда $p$ также делит

$f(m)-f(k) = (m-k)(m+k+1)$. Так как $m-k < m < p$, откуда

$p \mid m+k+1 < m+1+k+1 < 2p$, следовательно $m+k+1=p$.

Аналогично $k+l+1=p$, значит $m=l$, что невозможно - противоречие.