# Polynomials - Relation of Divisibility

The exercise I am having difficulty solving is the following one :

Suppose $P$ and $Q$ are two polynomials with integer coefficients. Suppose also that for all $(m,n) \in \mathbb{Z}^2$ we have $P(m)-P(n) | Q(m)-Q(n)$. Show that there exists a polynomial $H \in \mathbb{Q}[X]$ such that $Q= H \circ P$.

The issue is that I do not now how to characterize effectively the existence of such a polynomial $H$... I have tried, without success, to use the following result :

if $P,Q$ are two polynomials with integer coefficients such that $P(n)|Q(n)$ for infinitely many integers $n$, then $P$ divides $Q$ within $\mathbb{Q}[x]$.

Does anyone have an idea ?

(Fried-MacRae) Let $K$ be an arbitrary field, and let $f(t),g(t),f_1(t)$ and $g_1(t)$ be polynomials in $K[t]$. Then $f_1(x)-g_1(z)$ divides $f(x)-g(z)$ in $K[x,z]$ if and only if there exists a polynomial $F(t)$ in $K[t]$ such that $f(t)=F(f_1(t))$ and $g(t)=F(g_1(t))$.
• @Marsan. If think you can prove Fried-MacRae's result without Galois Theory. One idea is writing the polynomial $f(x)$ is basis $f_1(x)$. That is, – MathChat Jan 6 '17 at 4:01
• write $$f(t)=a_n(t)f_{1}(t)^n+\cdots+a_1(t)f_{1}(t)+a_0(t)$$ where $\deg a_{i}(t)<\deg f_{1}(t)$ for all $i=0,\ldots,n$. Thus, the polynomial $F(T)=a_n(t)T^n+\cdots+a_1(t)T+a_0(t) \in K(t)[T]$ is such that $F(f_1(t))=f(t)$. Now find a similar polynomial $G(T) \in K(t)[T]$ such that $F(g_1(t))=g(t)$. Then, try to see if the divisibiity condition will let you conclude that $F(T), G(T) \in K[T]$ and that they are the same polynomial. – MathChat Jan 6 '17 at 4:14