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

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

For $k = 0$, take $c_0 = \sqrt[L]{a_u/b_v}$, so $Q(c_0 x^L) = a_u x^u + \dots = P(x) + O_{u-1}(x)$.
Assume $g_{k-1}(x) = c_0 x^L + \dots + 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{align*} 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{align*}$$
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}. \qquad (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 \binom{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 \binom{L+1}{k} r_{m+k} = \sum_{k=0}^{L+1} (-1)^k \binom{L+1}{k} 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 $\deg(Q)$ divides $\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_1x^u + \dots$ and $h_2(x) = c_2x^u + \dots$ satisfying
$$P(x^v) \equiv Q(h_1(x)), \quad P(2x^v) \equiv Q(h_2(x)).$$
Comparing leading coefficients gives:
$$a_u = b_v \cdot c_1^v \quad \text{and} \quad 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., $\deg(Q)$ divides $\deg(P)$.

Proof 3 for (2): Choosing $f(x) = x^v$, there exists a rational-coefficient polynomial $h(x) = c_ux^u + c_{u-1}x^{u-1} + \dots + 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) + \dots + xh_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) + \dots + xh_1(p) + h_0(p) - D.$$
The right-hand side has degree $\leq 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., $\deg(Q)$ divides $\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 \neq 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 \neq 0$ and $r \not\equiv u \pmod 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 \binom{v}{1} (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 $\deg(Q) = v$ divides $\deg(P) = u$. $\square$