Let $f(x)$ be a non-constant polynomial with integer coefficients. It is a well-known result that if $f(n)$ is a square for all integers $n$, then $f$ must in fact be the square of a polynomial (see, for example: <http://www.mast.queensu.ca/~murty/poly2.pdf>).


My question is the following. Suppose that $\deg f = d$, and suppose that for every integer $n$, we have that $f(n)$ is a perfect $k$-th power for some $k\_n > 1$ dividing $d$. I want to emphasize that $k\_n$ is allowed to depend on $n$. For instance, it could be the case that $f$ is of degree $6$ and $f(2) = 2^3$ while $f(3) = 3^2$, and $f(n)$ is either a square or a cube (or both) for every $n$. 


Can we conclude that $f$ is a perfect $m$-th power, for some $m > 1$ dividing $d$?



Polynomials which always assume perfect power values
Here is a more elementary argument than that of nfcd23. It only assumes that $f(n)$ is a $k$th power for *some* $k$ depending on $n$, which need not be assumed to divide $d$. Over $\mathbf{C}$, write


$$f(x) = C \prod (x - \alpha\_i)^{r\_i},$$


where the $\alpha\_i$ are distinct. 
By Cebotarev, (or more simply, by Frobenius), we may find infinitely many primes $p$ such that $p$
 splits completely in $K = \mathbf{Q}(\alpha\_i)$, and in addition, $p$ is prime to both $C$ and the difference $\alpha\_i - \alpha\_j$ of any pair of distinct roots. (The last two conditions hold automatically for all but finitely many primes.)


For each root $\alpha\_i$, choose a prime $p\_i$ of this form.
Then choose an integer $n$ (using the Chinese Remainder Theorem)
such that:


$$\text{$n$ is congruent to $\alpha\_i$ modulo $p\_i$ but not modulo $p^2\_i$.}$$ 


This ensures that the $p\_i$-adic valuation of $f(n)$ is $r\_i$ for each $i$, because that is the valuation of $(n - \alpha\_i)^{r\_i}$, and by assumption, $p\_i$ does not divide any of the other terms. If $f(n)$ is a perfect $k$th power, this implies that the greatest common divisor $r$ of all the $r\_i$ must be divisible by $k$, and hence equal to $mk$ where $k > 1$.
 But that implies that $f(x) = A g(x)^{mk}$ for some $g(x)$. Once again letting $x = n$ and noting that $f(n)$ is a $k$th power, we deduce that $A = B^k$, and so


$$f(x) = B^k g(x)^{mk} = (B g(x)^m)^k.$$


