Азиатско-Тихоокеанская математическая олимпиада, 2025 год

Пусть $P(x)$ — непостоянный многочлен с целыми коэффициентами такой, что $P(0) \neq 0$. Пусть $a_1$, $a_2$, $a_3$, $\ldots$ — бесконечная последовательность целых чисел такая, что для любых различных натуральных $i$ и $j$ разность ${a_i-a_j}$ делится на $P{(i - j)}$. Докажите, что последовательность $a_1$, $a_2$, $a_3$, $\ldots$ должна быть постоянной, то есть существует константа $c$, такая что $a_n = c$ для всех положительных $n$.

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

Лемма (Шура): Пусть $P(x)\in\mathbb Z[x]$ — неприводимый (непостоянный) многочлен. Обозначим

$S={p\ \text{простое}:\ \exists n \in\mathbb Z\text{ такое, что }p\mid P(n)}.$

Тогда $S$ бесконечно.

Доказательство

Рассмотрим три случая.

1. Если $P(0)=0$, то очевидно что $S$ бесконечно.

2. Пусть $P(0)=1$ тогда возьмем что $S$ конечно. Возьмем самый наибольший простой делитель как $p$. Взяв $n>p$ заметим что $P(n!) \equiv P(0) \equiv 1 \pmod {p_1p_2…p_kp}$ отсюда $P(n!)$ не делится ни на один из простых чисел из $S$.

3. Пусть $P(0)=1,0$. Рассмотрим многочлен

$$g(x)=\frac{P(x\cdot P(0))}{P(0)}.$$

Так как $P(0)\in\mathbb Z$ и коэффициенты $P$ — целые, то $g(x)\in\mathbb Z[x]$, и при этом $g(0)=1$. (Действительно, при разложении $P(x)=a_dx^d+\dots+a_1x+a_0$ имеем

$$P(xP(0))=a_d(xP(0))^d+\dots+a_1(xP(0))+a_0,$$

и деление на $P(0)=a_0$ даёт целые коэффициенты у многочлена $g$.)

И так же как во втором случае $S$-бесконечно.

Это доказывает лемму Шура. $\square$

⸻

Теперь так как $P(0) \neq 0$ тогда по шуре сущ. бесконечно простых $p$ таких что $p | P(k)$ но $k$ не делится ( из $k | P(k)-P(0)$). По теореме безу найдутся такие $m,n$ что $m(k+p)+np=gcd(k+p,p)=1$ тогда:

$P(k) \equiv P(k+(m+n)p) \equiv 0 \pmod p$ и так как $a_{j+1}-a_j : p$ отсюда $a_{j+ k+(m+n)p} \equiv a_{j+2k+(m+n)p} \equiv … \equiv a_{j+km+(m+n)p} \equiv a_{j+1} \equiv a_j$ =>> $a_{j+1}-a_j : p$ для бесконечно много $p$ и отсюда $a_{j+1}=a_j$.