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

Дано натуральное число $n$ и простое число $p$. По условию произведение $P = \prod_{k=1}^n (k^3 + 1)$ делится на $p^3$.

Разложим каждый множитель по формуле суммы кубов $k^3 + 1 = (k + 1)(k^2 - k + 1)$:

$$P = \prod_{k=1}^n (k + 1) \cdot \prod_{k=1}^n (k^2 - k + 1) = (n + 1)! \cdot \prod_{k=1}^n (k^2 - k + 1)$$

Предположим от противного, что $p > n + 1$.

Так как $p > n + 1$, число $(n + 1)!$ не содержит простых множителей $p$, то есть $\gcd((n + 1)!, p) = 1$. Следовательно, произведение $B = \prod_{k=1}^n (k^2 - k + 1)$ должно делиться на $p^3$.

Оценим максимальное значение каждой скобки $k^2 - k + 1$ при $1 \le k \le n$. Так как $n \le p - 2$, имеем:

$$k^2 - k + 1 \le n^2 - n + 1 < n^2 \le (p - 2)^2 = p^2 - 4p + 4 < p^2$$

Так как $k^2 - k + 1 < p^2$, ни один из множителей $k^2 - k + 1$ не может делиться на $p^2$. Значит, каждый такой множитель может вносить в разложение произведения $B$ не более одной первой степени $p$.

Сравнение $k^2 - k + 1 \equiv 0 \pmod p$ эквивалентно $(2k - 1)^2 \equiv -3 \pmod p$. Квадратное сравнение по модулю простого числа $p$ имеет не более двух решений. Так как $1 \le k \le n < p$, все значения $k$ дают различные остатки по модулю $p$.

Следовательно, среди чисел $k \in \{1, \dots, n\}$ существует не более двух значений, для которых $k^2 - k + 1 \vdots p$.

Таким образом, произведение $B$ может делиться максимум на $p^2$, что противоречит тому, что $P \vdots p^3$.

Полученное противоречие показывает, что $p \le n + 1$.