Polynomials which always assume perfect power values 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$?
 A: 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.$$
A: Here is an argument avoiding Siegel's theorem (and also seemingly different from the DLS argument to which Dimitrov refers, as the main tool I will use is Weil's RH for absolutely irreducible curves whereas DLS use arguments based on Hilbert irreducibility).
Let $S$ be a non-empty finite set of primes (e.g., the primes factors of $d$) and consider $f \in \mathbf{Z}[X]$ that is not an $e$th power in $\mathbf{Z}[X]$ (equivalently, in $\mathbf{\mathbf{Q}}[X]$) for each $e \in S$. An elementary argument with the monic multiple of $f$ shows that for each of the primes $e \in S$ the polynomial $f$ either (i) is not an $e$th power in $\overline{\mathbf{Q}}[X]$ or (ii) is of the form $c h^e$ 
for some monic $h$ with $c$ the leading coefficient of $f$. 
If there is any integer $n$ away from zeros of $f$ such that $f(n)$ is an $e$th power for some $e$ as in case (ii) then $c$ is an $e$th power and hence so is $f$.  Thus, we can assume for our purposes that case (ii) never occurs. 
Since each $e\in S$ is prime, it follows that the polynomial $Y^e - f(X)$ is irreducible in $\overline{\mathbf{Q}}[X,Y]$ (as it is the same to be irreducible in $\overline{\mathbf{Q}}(X)[Y]$, for which $f$ not being an $e$th power in $\overline{\mathbf{Q}}(X)$ is equivalent to the irreducibility property since $e$ is prime). 
We conclude that $Y^e - f(X)$ is absolutely irreducible over $\mathbf{Q}$ for every $e \in S$. Hence, for all large primes $p$, $Y^e - f(X)$ is absolutely irreducible over $\mathbf{F}_p$ too. (Recall that "absolute irreducibility" is inherited under reduction modulo all but finitely many primes, whereas ordinary irreducibility is not.) In what follows, only consider such $p$ (moreover big enough so that $f \bmod p$ has the same degree as $f$).  
These curves $Y^e - f(X) = 0$ for varying $e \in S$ (if $\#S > 1$) have finite overlap in characteristic 0, so they are pairwise disjoint up to uniformly bounded error in characteristic $p$ for large $p$. Hence, the solution set $V_p$ to $h \equiv 0 \bmod p$ is the "disjoint" (up to bounded amount) union of the solutions sets to the individual curves $C_{e,p} := \{y^e - f(x) = 0\}$.  There are at most $d := \deg(f)$ values $x \in \mathbf{F}_p$ where $f$ vanishes mod $p$, over which there is only one point $(x,0)$ in $V_p$. Ignoring those at most $d$ points, as well as the uniformly bounded overlaps sets for distinct $e$'s just mentioned, every other fiber of $V_p$ over the $x$-line $\mathbf{F}_p$ lies in exactly one of the curves $C_{e,p}$. 
Consider $p \equiv 1 \bmod e$ for all $e \in S$. The fibers for $C_{e,p}$ have size $e$ (away from zeros of $f$ in $\mathbf{F}_p$).  As $p$ grows, $\#C_{e,p}(\mathbf{F}_p) \sim p$ for each $e \in S$, by RH, so the image of $C_{e,p}$ in $\mathbf{F}_p$ consists of $\sim p/e$ points as $p$ grows. 
Varying through all $e \in S$, if $V_p$ actually hits the entire $x$-line for all such large $p$ (say even up to a bounded amount as such $p$ grows) we would get 
$\sum_{e \in S} 1/e = 1$ (equality on the nose, not just approximation). But the $e$'s are pairwise distinct primes, so no such equality is possible (look at it $e_0$-adically for one $e_0 \in S$).
Thus, for (many) large $p$ the projection $x: V_p \rightarrow \mathbf{F}_p$ is not surjective, so if $n \in \mathbf{Z}$ represents a mod-$p$ residue class not in the image then for every $e \in S$ the congruence $y^e \equiv f(n) \bmod p$ has no solution, so certainly for every $e \in S$ the integer $f(n)$ is not an $e$th power in $\mathbf{Z}$ as well.
QED
