China-TST-2025A

Proof 1: We denote by $O_k(x)$ any polynomial of degree at most $k$.

(1) If $v=\mathrm{deg}Q$ divides $u=\mathrm{deg}P$, let $u=vL$. Write $$P(x)=a_u{x}^u+a_{u-1}{x}^{u-1}+\cdots +a_0,$$ $$Q(x)=b_v{x}^v+b_{v-1}{x}^{v-1}+\cdots +b_0.$$

For $k=0$, take $c_0=\sqrt[L]{a_u/b_v}$, so $Q(c_0{x}^L)=a_u{x}^u+\cdots =P(x)+O_{u-1}(x)$. Assume $g_{k-1}(x)=c_0{x}^L+\cdots +c_{k-1}{x}^{L+1-k}$ satisfies $Q(g_{k-1}(x))=P(x)+R(x)$, where $R(x)=s{x}^{u-k}+\dots$ has degree $\le u-k$. Consider $g_k(x)=g_{k-1}+c_k{x}^{L-k}$: $$\begin{array}{rl}Q(g_k(x))-Q(g_{k-1}(x))& =b_v[(g_{k-1}(x)+c_k{x}^{L-k}{)}^v-(g_{k-1}(x){)}^v]+O_{(v-1)L-k}(x)\\ & =b_v[v{g}_{k-1}(x{)}^{v-1}{c}_k{x}^{L-k}+O_{(v-2)L+2(L-k)}(x)]+O_{(v-1)L-k}(x)\\ & =c_k{b}_{v}v{c}_0^{v-1}{x}^{vL-k}+O_{u-k-1}(x).\end{array}$$ Choose $c_k$ such that $c_k{b}_{v}v{c}_0^{v-1}=s$ (the coefficient of $x^{vL-k}$ in $R(x)$). Then $g_k(x)=g_{k-1}+c_k{x}^{L-k}$ satisfies $Q(g_k(x))-P(x)=O_{u-k-1}(x)$.

The problem's condition guarantees that for every integer $m\ge M_0$, there exists $n=n_m$ such that $Q(n_m)=P(m)$, thus $$|Q(n_m)-Q(h(m))|=|P(m)-Q(h(m))|=|R(m)|\le C\cdot m^{u-L-1}.$$ This implies that when $M_0$ is sufficiently large, there exists a positive real number $D$ such that for all integers $m\ge M_0$: $$|n_m-h(m)|<\frac{D}{m}.(11)$$

Let $n_m=h(m)+r_m$. Since $h(m)$ is a polynomial of degree $L$, we have $$\sum _{k=0}^{L+1}(-1{)}^k(\genfrac{}{}{0ex}{}{L+1}{k})h(m+k)=0.$$ However, since each $n_m$ is an integer, this implies $$T_m=\sum _{k=0}^{L+1}(-1{)}^k(\genfrac{}{}{0ex}{}{L+1}{k})r_{m+k}=\sum _{k=0}^{L+1}(-1{)}^k\left(\genfrac{}{}{0ex}{}{L+1}{k}\right)n_{m+k}\in \mathbb{Z}.$$ From (11), there exists $M_1$ such that when $m\ge M_1$, we have $|r_m|<\frac{1}{2^{L+1}}$, and consequently $T_m=0$. This means $r_m$ is a recurrence sequence, and solving this recurrence shows that for $m\ge M_1$, $r_m$ is a polynomial in $m$ with degree at most $L$. Moreover, from (11) we know $\{r_m\}$ is bounded, hence it must be identically zero. Therefore, $P(m)-Q(h(m))=0$ holds for all $m\ge M_1$, which implies $P(x)\equiv Q(h(x))$. Furthermore, since $h(m)=n_m$ always takes integer values, $h(\cdot )$ must be a polynomial with rational coefficients.

(2) Prove that $\mathrm{deg}(Q)$ divides $\mathrm{deg}(P)$.

Proof 2 for (2): Following similar analysis to Proof 1, we select $f_1(x)=x^v$ and $f_2(x)=2x^v$, which yields rational-coefficient polynomials $h_1(x)=c_1{x}^u+\dots$ and $h_2(x)=c_2{x}^u+\dots$ satisfying $$P(x^v)\equiv Q(h_1(x)),P(2x^v)\equiv Q(h_2(x)).$$ Comparing leading coefficients gives: $$a_u=b_v\cdot c_1^v\text{and}{a}_u\cdot 2^u=b_v\cdot c_2^v,$$ thus $2^u={\left(\frac{c_2}{c_1}\right)}^v$, meaning $2^{u/v}=\frac{c_2}{c_1}$ must be rational. Since fractional powers of 2 are irrational, $\frac{u}{v}$ must be an integer, i.e., $\mathrm{deg}(Q)$ divides $\mathrm{deg}(P)$.

Proof 3 for (2): Choosing $f(x)=x^v$, there exists a rational-coefficient polynomial $h(x)=c_u{x}^u+c_{u-1}{x}^{u-1}+\cdots +c_0$ satisfying $P(x^v)\equiv Q(h(x))$, where for large positive integers $m=x^v$, $n_m=h(x)$ is also a positive integer. Grouping terms by powers modulo $v$, we express $h(x)$ as: $$h(x)\equiv x^{v-1}{h}_{v-1}(x^v)+x^{v-2}{h}_{v-2}(x^v)+\cdots +x{h}_1(x^v)+h_0(x^v),$$ where each $h_k(\cdot )$ is a rational-coefficient polynomial. For a large prime $p$, substituting $x=p^{1/v}$ yields $h(p^{1/v})=D\in \mathbb{Z}$. By Eisenstein's criterion, the polynomial $x^v-p$ is irreducible and shares the root $x=p^{1/v}$ with $h(x)-D$, hence $x^v-p\mid h(x)-D$. For $k=0,1,\dots ,v-1$, we have $x^v-p\mid h_k(x^v)-h_k(p)$, therefore: $$x^v-p\mid x^{v-1}{h}_{v-1}(p)+x^{v-2}{h}_{v-2}(p)+\cdots +x{h}_1(p)+h_0(p)-D.$$ The right-hand side has degree $\le v-1$, so divisibility implies it's the zero polynomial. Thus for $k=1,2,\dots ,v-1$, $h_k(p)=0$ holds for all large primes $p$, making each $h_k(x)$ identically zero. Consequently, $h(x)\equiv h_0(x^v)$, meaning the degree $u$ must be a multiple of $v$, i.e., $\mathrm{deg}(Q)$ divides $\mathrm{deg}(P)$.

Proof 4 for (2): Again choosing $f(x)=x^v$, there exists a rational-coefficient polynomial $h(x)=c_u{x}^u+c_{u-1}{x}^{u-1}+\cdots +c_0$ ($c_u\ne 0$) satisfying $P(x^v)\equiv Q(h(x))$. We claim that all terms in $h(x)$ must have exponents congruent to $u$ modulo $v$ or be constant terms. If not, let $r$ be the largest exponent with $c_r\ne 0$ and $r\not\equiv u(\mathrm{mod}v)$ ($r>0$). Since $Q(x)=b_v{x}^v+b_{v-1}{x}^{v-1}+\cdots$, we have: $$Q(h(x))=b_v(h(x){)}^v+O(u(v-1)),$$ where $O(u(v-1))$ denotes some polynomial of degree $\le u(v-1)$. In the expansion of $b_v(h(x){)}^v$, there exists a term: $$b_v\cdot \left(\genfrac{}{}{0ex}{}{v}{1}\right)(c_u{x}^u{)}^{v-1}\cdot c_r{x}^r=b_{v}v{c}_u^{v-1}{c}_r\cdot x^{uv-u+r},$$ while other terms either have exponents divisible by $v$ or exponents less than $uv-u+r$, leaving no cancellation possible. Thus $P(x^v)=Q(h(x))$ would contain a non-zero $x^{uv-u+r}$ term whose exponent isn't divisible by $v$ - a contradiction.

Let $t$ be the smallest non-negative remainder of $u$ modulo $v$. Then $h(x)$ can be expressed as $x^{t}g(x^v)+c_0$, where $g(\cdot )$ has rational coefficients. From $P(x^v)\equiv Q(h(x))$, when $y=x^v$ is a large positive integer, $h(x)=h(y^{1/v})=y^{t/v}g(y)+c_0$ must also be integer-valued. This implies $y^{t/v}$ must be rational for all large positive integers $y$, forcing $t=0$. Therefore $\mathrm{deg}(Q)=v$ divides $\mathrm{deg}(P)=u$. $\square$