Азиатско-Тихоокеанская математическая олимпиада, 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$.

Обозначим $a_0 = P(0) \neq 0$. Существует бесконечно много простых $p$, делящих $P(n)$ но не $n$. Действительно, $n \mid P(n) - a_0$, $(P(n),n) = (n, a_0) \le a_0$, потому выберем $n$ такой, что все его простые делители больше $a_0$. Поскольку $P(n) \mid a_{n+i} - a_i$, $p \mid a_{n+i} - a_i$. Более того, $P(p+n) \equiv P(n) \equiv 0 \pmod{p}$, потому $p \mid a_{n+p+i} - a_i$. Тогда $a_i \mod p$ периодически с периодом $n$ и $n+p$. По теореме Безу $(n,n+p) = 1$ тоже период, т.е. $p \mid a_{i+1} - a_i$ для всех $i$ и $p$ таких, что $p \mid P(n)$ и $p \nmid n$ для некого $n$. Т.к. таких простых $p$ бесконечно много, $a_{i+1} - a_i$ делится на бесконечно много простых, откуда $a_{i+1} = a_i$, что и требовалось. $\blacksquare$