40-я Балканская математическая олимпиада. Анталья, 2023 год

Для каждого положительного целого числа $n$, обозначим через $\omega(n)$ количество различных простых делителей $n$ (например, $\omega(1)=0$ и $\omega(12)=2$ ). Найдите все многочлены $P(x)$ с целочисленными коэффициентами такие, что если $n$ является положительным целым числом, удовлетворяющим неравенству $\omega(n)>2023^{2023}$, то $P(n)$ также является положительным целым числом и верно неравенство $$\omega(n) \geq \omega(P(n))$$

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

Ответ: Все полиномы вида $f(x) = x^m$ для некоторого $m ∈ Z+$ и $f(x)=c$ for some $c ∈ Z+ с$ $ω(c)≤2023^{2023}+1$.

Прежде всего докажем следующую (хорошо известную) лемму. Лемма: Пусть $f(x)$ — непостоянный многочлен с целыми коэффициентами. Тогда количество простых чисел p таких, что $p|f(n$) для некоторого n, бесконечно.

Доказательство. Если $f(0) = 0$, то лемма очевидна. В противном случае определим полином $g(x) = \frac{f(xf(0))}{f(0)}$

который имеет целые коэффициенты. Заметим, что $g(0) = 1$, и если g удовлетворяет свойству леммы, то то же самое делает и f. Итак, нам нужно доказать, что существует бесконечно много простых чисел p таких, что $p|g(n)$ для некоторого n. Предположим, от противного, что число таких простых чисел конечно, и пусть это $p_1, ..., p_k$. Затем положим $n = Np_1 · · · p_k$ для некоторого большого N такого, что $|g(n)| > 1$. Очевидно, что $g(n)$ имеет простой делитель, но не является ни одним из чисел $p_j$. Это противоречие, и отсюда следует следующий результат.

Пусть $M = 2023^{2023} + 1$. Заметим, что постоянные многочлены $f(x) = c$ с $c ∈ N$ такие, что $ω(c) ⩽ M$ удовлетворяют условиям задачи. С другой стороны, если $f(x) = c$ с $ω(c) > M$, мы можем выбрать такое n, что $ω(n) = M$, чтобы увидеть, что условие задачи не выполняется. Далее ищем непостоянные полиномы, удовлетворяющие условиям задачи. Пусть f(x) = x^mg(x), где $m ≥ 0$ и $g(x)$ – многочлен с $g(0)$ неравен 0. Мы утверждаем, что g – постоянный многочлен. Действительно, если это не так, то (по лемме) существуют попарно различные простые числа $q_1,...,q_M+1$ и ненулевые целые числа $n_1,...,n_M+1$ такие, что $q_i > |g(0 )$| и $q_i|g(n_i)$ для $i = 1,2,...,M + 1$. Положим $n = p_1p_2 ···p_M$, где $p_1, ..., p_M$ — различные простые числа такие, что

$p_1 ≡n_i (mod q_i)$, $∀i=1,2,...,M+1$

$p_j ≡1 (mod q_i)$, $∀i=1,2,...,M+1$, $∀j=2,3,...,M$.

Заметим, что, поскольку $q_i > |g(0)|$, невозможно иметь $q_i|n_i$, поэтому существование таких простых чисел гарантируется китайской теоремой об остатках и теоремой Дирихле. Теперь для каждого $i=1,2,...,M+1$ мы видим, что $n=p1···pM ≡ni (mod q_i)$, а это означает, что

$g(n)≡g(ni)≡0 (modq_i)$ $∀i=1,2,...,M+1$.

Таким образом, $ω(f(n)) ≥ ω(g(n)) ≥ M + 1 > M = ω(n)$, что приводит к искомому противоречию. Следовательно, $f(x) = cx^m$ для некоторого m ≥ 1 (поскольку f непостоянно). Если c < 0, возьмем некоторое n такое, что $ω(n) = M$, и увидим, что $f(n)$ отрицательна и, следовательно, не удовлетворяет условиям задачи. Если c > 1, выберите некоторое n такое, что $ω(n) = M$ и $gcd(n, c) = 1$, чтобы заметить, что f не может удовлетворять условиям задачи. Это означает, что $f(x) = x^m$ (что наверняка является решением проблемы) для некоторого m≥1 и $f(x)=c$f для некоторого $c ε Z+$ с$ω(c) ≤ M$ — единственные полиномы, удовлетворяющие условиям задачи