Композиция полиномов

[domna]

Пусть числа $1,2,\dots, N$, где $N$ - составное, являются корнями полинома $P(x),\ deg\ P=N$. При каких условиях существуют полиномы $Q$, $S$, $deg\ S>1,\ deg\ Q>1$, $deg\ S \times deg\ Q=N$, такие что $P(x)=Q(S(x))$. В частности, возможно ли такое при $N=999,\ deg\ Q=27,\ deg\ S=37$?

[RIP]

Док-во невозможности при $N=999,\deg Q=27,\deg S=37$:
Допустим, что $P(x)=Q(S(x))$. Запишем $Q(x)=a(x-\alpha_1)(x-\alpha_2)\ldots(x-\alpha_{27})$. Подставляем в равенство $P(x)=Q(S(x))$ точки $x=1,2,\ldots,999$ и получаем, что

$$\{1,2,\ldots,999\}=\bigsqcup_{k=1}^{27}A_k,\#A_k=37,\quad\forall m\in A_k\ \ S(m)=\alpha_k.$$

Но тогда для любого $k=1,2,\ldots,27$ выполняется

$$S(x)=\alpha_k+b\prod_{\beta\in A_k}(x-\beta),$$

в частности, получаем, что $\sum\limits_{\beta\in A_k}\beta^2$ не зависит от $k$. Но тогда число $1^2+2^2+3^2+\ldots+999^2=\frac{999\cdot1000\cdot1999}{6}$ должно делиться на $27$, что, очевидно, не так. Противоречие.

Добавлено спустя 37 минут 10 секунд:

Вообще, вопрос сводится к тому, для каких натуральных $N,n,m$, удовлетворяющих условию $N=nm$, можно множество $\{1,2,\ldots,N\}$ представить в виде объединения $n$ попарно непересекающихся множеств из $m$ элементов каждое:

$$\{1,2,\ldots,N\}=\bigsqcup_{k=1}^nA_k,\ \#A_k=m,$$

чтобы при каждом $j=1,2,\ldots,m-1$ сумма $\sum\limits_{\beta\in A_k}\beta^j$ не зависела от $k$.
Но не думаю, что это поможет в решении общего случая.

P.S. Легко видеть, что если $N$ делится на $2$, то можно подобрать многочлены степеней $\deg Q=\frac N2$ и $\deg S=2$.