By using induction(recurence) on $ deg f$. Suppose that $ deg f < deg g$. Then $ f(x) - f(y)$ can be as a polynomial in$ x$, which has smaller degree than $ g(x) - g(y)$, another polynomial in$ x$ which is a factor. Thus $ f(x) - f(y) = 0$, so $ f(x) = Constant$ and we can take $ h(x)$ to be the same constant. So the result is true. Now suppose the result is true for $ degree < deg f$. Put $ F(x) = f(x) - f(0)$, $ G(x) = g(x) - g(0)$, so that$ F(0) = G(0) = 0$and $ deg F = deg f$. Also$ F(x) = a(x,0) G(x)$. Put $ h(x) = a(x,0)$, so that $ F(x) = h(x) G(x)$. Hence $ F(x) - F(y) = h(x)G(x) - h(y)G(y) = (h(x) - h(y))G(x) +h(y)(G(x) - G(y))$. Hence $ G(x) - G(y)$ divides $ (h(x) - h(y))G(x)$. But $ G(x) - G(y)$ is relatively prime to $ G(x)$, so it must divide $ h(x) - h(y)$. In other words, $ h(x) - h(y) = b(x,y)(G(x) - G(y))$. But $ deg h < deg f$, so we have $ h(x) = H(G(x))$ for some $ H$. Then $ f(x) = G(x)H(G(x))$ which is a function of $ G(x)$ as required.

n-naoufal wrote: Hence $ F(x) - F(y) = h(x)G(x) - h(y)G(y) = (h(x) - h(y))G(x) + h(y)(G(x) - G(y))$. Hence $ G(x) - G(y)$ divides $ (h(x) - h(y))G(x)$. How is the last "hence" proven?

orl wrote: Let $ f, g$ and $ a$ be polynomials with real coefficients, $ f$ and $ g$ in one variable and $ a$ in two variables. Suppose \[ f(x) - f(y) = a(x, y)(g(x) - g(y)) \forall x,y \in \mathbb{R}\] Prove that there exists a polynomial $ h$ with $ f(x) = h(g(x)) \text{ } \forall x \in \mathbb{R}.$ Lemma 1: If $f(x) = x^m$ and $g(x) = x^n$ satisfy the equation, then $m$ must be a power of $n$. Proof: Let $c(x) = b(x,1)$. We have that $c(x) = \frac{x^m - 1}{x^n - 1}$ for all $x$, so the polynomial $x^n - 1$ divides the polynomial $x^m - 1$. Hence, if $\omega$ is a primitive $n$th root of unity, $\omega^n - 1 = \omega^m - 1 = 0$, whence $n | m$. $\blacksquare$ Lemma 2: $\deg g$ divides $\deg f$. Proof: Because we may scale $a(x,y)$, we may suppose without loss of generality that $f$ and $g$ are monic. Let $\deg f = m$ and $\deg g = n$. Let $b(x,y)$ be the sum of the monomials in $a(x,y)$ with degree $m-n$. Because the degree of $a(x,y)$ is $m-n$, the only monomials with degree $m$ that can be obtained by multiplying $a(x,y)$ by $g(x) - g(y)$ are obtained by multiplying $b(x,y)$ with $x^n - y^n$. Equating the terms with degree $m$ on both sides of the original equation, we find that $x^m - y^m = b(x,y) (x^n - y^n)$. By lemma 1, it follows that $n$ divides $m$. $\blacksquare$ For a fixed polynomial $g$, we perform strong induction on the degree of $f$. The base case, $\deg f = \deg g$, is obvious since $a(x,y)$ must be constant. Suppose now that the result is true for all polynomials with degree less than $\deg f$. By lemma 2, $n \deg g = \deg f$ for some positive integer $n$. By the division algorithm, we can find some real $k$ and some polynomial $r(x)$ with degree less than $\deg f$ such that $f(x) = k g(x)^n + r(x)$. Hence, we have $f(x) - f(y) = k(g(x)^n - g(y)^n) - (r(x) - r(y))$. Because $g(x) - g(y)$ divides $f(x) - f(y)$ and $g(x)^n - g(y)^n$, it must divide $r(x) - r(y)$ as well, so by the inductive hypothesis $r(x) = h_0(g(x))$ for some polynomial $h_0$. Setting $h(x) = h_0(x) + kx^n$, we find that $h(g(x)) = h_0(g(x)) + k g(x)^n = f(x)$, so we are done. Third Edition wrote: How is the last "hence" proven? $G(x) - G(y)$ must divide $F(x) - F(y)$ (because of the original equation.)