17-я Международная Жаутыковская олимпиада по математике, 2021 год

Пусть $P(x)$ — непостоянный многочлен степени $n$ с рациональными коэффициентами, который нельзя представить в виде произведения двух непостоянных многочленов с рациональными коэффициентами. Докажите, что количество многочленов $Q(x)$ с рациональными коэффициентами, степени, меньшей $n$, таких, что $P(Q(x))$ делится на $P(x)$,
   а) конечно;
   б) не превосходит $n$. ( А. Голованов )

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

Решение: Пусть $x_1,\ldots,x_n$ $-$ все корни $P.$ Из условия следует, что $P(Q(x_1))=0,$ поэтому $Q(x_1)\in\{x_1,\ldots,x_n\}.$ Достаточно доказать, что для любого $i=1,\ldots,n$ существует не более одного такого многочлена $Q,$ что $Q(x_1)=x_i.$

От обратного, допустим, что $Q_1(x_1)=Q_2(x_1)=x_i\implies R=Q_1-Q_2\in\mathbb Q[x]$ имеет корень $x_1,$ а так же $0<\deg R<n.$

Тогда многочлен $G=\gcd(P,R)\in\mathbb Q[x]$ делит $P,$ тогда $P=G\cdot S,$ при этом $0<\deg G<n$ (поскольку это НОД двух многочленов, которые имеют общий корень), но это противоречит условию, ч.т.д. $\blacksquare$