ComplexPhi wrote: Let $p$ be an odd prime number. Determine the polynomials $f$ and $g$ from $\mathbb{Z}[X]$ such that \[f(g(X))=\sum_{k=0}^{p-1} X^k.\] For example $f(x)=\sum_{k=0}^{p-1}x^k$ and $g(x)=x$

Your post could prevent many people from seeing this problem, don't you think? It's perfectly clear for everyone the statement asks to determine ALL polynomials $f,g$...

dgrozev wrote: Your post could prevent many people from seeing this problem, don't you think? It's perfectly clear for everyone the statement asks to determine ALL polynomials $f,g$... Clear for everyone but for me. Sorry. I never play the stupid game "here is a badly stated / wrong / stupid / bad question. Please, modify the question in order to get a sympathic / clever / easy / interesting new problem and then solve it"

I edited the problem. Sorry for the previous bad wording .

Warning! The fact that it involves the cyclotomic $\Phi_p(X)$ is a herring. All that matters, for $p\geq 2$ not necessarily a prime (a fortiori odd), and the polynomial being monic, is that the coefficient of the monomial $X^{p-2}$ is of magnitude $1$. (One of the poorest problem in these tests, by my lights.)

Let $\omega$ be a primitive $n$-th root of $1$. (in our case any root except 1). Suppose there exists $f,g$ with $\deg f>1, \deg g>1$. Clearly $f(g(\omega^k))=0, k=1,2,\ldots,p-1$. Since $\deg f<p-1$, it's not possible all $g(\omega^k),k=1,2,\ldots,p-1$ to be pairwise different. Thus, there exist $i,j, 1\le i<j\le p-1$ with $g(\omega^i)=g(\omega^j)$. Hence $\omega$ is a root of $P(x)=g(x^i)-g(x^j)$, where we consider $P(x)$ overe the field $\mathbb{Z}_p$, or one can imagine that all monomials of $P$ are reduced to have degree less or equal to $p-1$. Since $\Phi_p(x)$ is the minimal polynomial having $\omega$ as a root, there are only two possibilities: 1) $P(x)\equiv \Phi_p(x)$, 2) $P(x) \equiv 0$. The first case is impossible since $P$ doesn't contain a monomial $x^0$. Let's consider the second case. Denote $A=\{k\in \mathbb{Z}_p \mid g \text{ contains the monomial }x^k \}$. Then, $g(x^i)\equiv g(x^j)$ implies \[i\cdot A=k\cdot A\] Hence, if one denote $\ell=i\cdot k^{-1}$, it holds: \[\ell \cdot A=A,\,\,\,\,\, \ell \neq 1\] For $m=\max A$ it must hold $ \ell \cdot m \leq m$ (over $\mathbb{Z}_p$), hence $ \ell \cdot m = m$, which is impossible.

Under the comments of my previous post, say the $RHS$ is any polynomial $P(X) \in \mathbb{Z}[X]$ of $\deg P = p-1$, with $p\geq 5$ (not necessarily a prime), and the coefficient of the monomial $X^{p-2}$ being of magnitude $1$. We want to show it cannot be written as $P(X) = f(g(X))$, with $f(X),g(X) \in \mathbb{Z}[X]$, $\deg f = u > 1$, $\deg g = v > 1$ (and obviously $uv=p-1$). Let then \[f(X) = a_uX^u + a_{u-1}X^{u-1} + \cdots + a_1 X + a_0,\] \[g(X) = b_vX^v + b_{v-1}X^{v-1} + \cdots + b_1 X + b_0.\] The coefficient of $X^{p-2}$ in $f(g(X))$ is clearly $ua_ub_v^{u-1}b_{v-1}$, since the next monomials are of degrees at most $\max\{p-3,p-v-1\}\leq p-3$. But $|ua_ub_v^{u-1}b_{v-1}| \neq 1$ (since $u\geq 2$), and thus cannot be equal to the coefficient of $X^{p-2}$ in $P(X)$. That's all, folks!

$f(g(x)) = \frac{x^p-1}{x-1} \implies f'(g(x+1)).g'(x+1) = (p-1)x^{p-2} +\frac{px(x+1)^{p-1} -(x+1)^p+1-px^p+x^p}{x^2}$ , which is irreducible by Einsenstein criterion then $deg (g) = 1$ or $deg (f) = 1$

The answer is \(g(x)\equiv\pm x+c\) for any \(c\) (and \(f\) easily extractable). These clearly work, so we show they are the only solutions. We may verify by Eisenstein criterion that \[\frac d{dx}f(g(x+1))=(p-1)x^{p-2}+(p-2)\binom p1x^{p-3}+\cdots+\binom p{p-2}\]is irreducible. But then \(\frac d{dx}f(g(x))=g'(x)\cdot f'(g(x))\) must also be irreducible, so \(g\) is linear. Of course, \(g\) has leading coefficient \(\pm1\), so we are done.