More generally, let $k$ be an integer greater than $1$ and let $P$ be a polynomial of degree at most $k-2$ with integral coefficients. The polynomials $f$ and $g$ with integral coefficients satisfying the condition $f(g(X)) = X^k + X^{k-1} + P(X)$ are: $f(X) = (\pm X \mp a)^k + (\pm X \mp a)^{k-1} + P(\pm X \mp a)$ and $g(X) = \pm X + a$, where $a$ is an integer, and $f(X) = \pm X + b$ and $g(X) = \pm X^k \pm X^{k-1} \pm P(X) \mp b$, where $b$ is an integer — in both cases, the signs correspond to one another; for instance, $f(X) = (-X + a)^k + (-X + a)^{k-1} + P(-X + a)$ and $g(X) = -X + a$ are admissible, but $f(X) = (-X + a)^k + (-X + a)^{k-1} + P(-X + a)$ and $g(X) = X + a$ are not.

Clearly, $\deg f \ge 1$, $\deg g \ge 1$ and the leading coefficients of $f$ and $g$ are $\pm 1$.

If $\deg g = 1$, we immediately obtain the first pair of polynomials above.
If $\deg g > 1$, write $f(X) = \sum_{i=0}^{m} a_i X^i$ and $g(X) = \sum_{i=0}^{n} b_i X^i$, and notice that $f(g(X)) = a_m b_n^m X^{mn} + m a_m b_n^{m-1} b_{n-1} X^{mn-1} + \dots$. Identification of coefficients yields $a_m b_n^m = 1$ and $m a_m b_n^{m-1} b_{n-1} = 1$. The latter forces $m = 1$ which leads to the second pair of polynomials above.

The polynomial $\Phi_p(X) = \sum_{k=0}^{p-1} X^k$ is the $p$-th cyclotomic polynomial. With the sign convention in the previous solution, the required polynomials are either $f(X) = \pm X \mp a$ and $g(X) = \pm \Phi_p(X) + a$, where $a$ is an integer, or $f(X) = \Phi_p(\pm X \mp b)$ and $g(X) = \pm X + b$, where $b$ is an integer.

The proof relies upon the well known fact that both $\Phi_p$ and its (formal) derivative, $\Phi'_p(X) = \sum_{k=0}^{p-2} (k+1)X^k$, are irreducible in $\mathbb{Z}[X]$. This follows from Eisenstein's irreducibility criterion upon substitution $X \mapsto X+1$: $\Phi_p(X+1) = \sum_{k=0}^{p-1} \binom{p}{k+1} X^k$ and $\Phi'_p(X+1) = \sum_{k=0}^{p-2} (k+1) \binom{p}{k+2} X^k$.

Now take the derivative both sides of the relation in the statement to obtain $f'(g(x))g'(X) = \Phi'_p(X)$. Since $\Phi'_p(X)$ is irreducible in $\mathbb{Z}[X]$ and its coefficients are obviously jointly coprime, either $f'(g(x)) = \pm 1$ and $g'(X) = \pm \Phi'_p(X)$ or vice versa — as before, the signs correspond to one another. With the same convention for signs, in the former case, $g(X) = \pm \Phi_p(X) + a$ and $f(X) = \pm X \mp a$, where $a$ is an integer; in the latter, $g(X) = \pm X + b$ and $f(X) = \Phi_p(\pm X \mp b)$, where $b$ is an integer.

We show that if $\deg g > 1$, then $\deg g = p-1$. The remaining details are easily filled in and hence omitted.

To begin, let $\zeta = \cos(2\pi/p) + i \sin(2\pi/p)$, let $\alpha$ be a (complex) root of $f$, and let $\beta$ be a (complex) root of $g - \alpha$. Since $\Phi_p(\beta) = f(g(\beta)) = f(\alpha) = 0$, it follows that $\beta$ is one of the $\zeta^j$, $j = 1, \dots, p-1$. In particular, $g - \alpha$ has no multiple roots, for $\Phi_p$ has no such.

Now let $n = \deg g > 1$, and let $\zeta^{k_1}, \dots, \zeta^{k_n}$ be the roots of $g - \alpha$, where $1 \le k_1 < \dots < k_n \le p-1$. Since $g$ has integral coefficients, $a = \sum_{j=1}^n \zeta^{k_j}$ is integral, by the first Vieta relation, so $h = \sum_{j=1}^n X^{k_j} - a$ is a monic non-constant polynomial with integral coefficients. Since $\Phi_p$ is the minimal polynomial of $\zeta$ and $h(\zeta) = 0$, it follows that $\Phi_p$ divides $h$, so $\deg h \ge \deg \Phi_p = p-1$. On the other hand, $\deg h = k_n \le p-1$, so $\deg h = p-1$, and since $h$ is monic, it ...