We claim that all polynomials $P(x) = (\pm x+ c)^d$ work where $c$ is an arbitrary integer, and $d$ is any positive divisor of $m$. If $P(x) = (x+c)^d$ then picking $x = n^{\frac{m}{d}}-c$ gives $P(x) = n^m$ thus these works. If $P(x) = (-x+c)^d$ then picking $x = -n^{\frac{m}{d}}+c$ gives $P(x) = n^m$ thus these work as well. Now we show that these are the only solutions. Firstly letting $n=0$ implies that $P$ has an integer root. Let it be $-b$. Then $P(x) = P_{d-1}(x)\cdot (x+b)$ (Let $P_j(x)$ denote $\frac{P(x)}{(x+b)^{d-j}}$ in the induction). Now we inductively show that $(x+b) \mid P_i(x)$ if $i \geq 1$. Let $p$ be any prime. Then now to show that $x+b$ divides $P_i(x)$ let $P_i(x) = (x+b)Q(x) + R(x)$. But letting $n =p$ we get that $P(k)$ is a prime power, thus so is $k+b$ and $P_i(k)$. If $i>1$ then letting $p$ be large shows that $|k|$ is large and $| P_i(k) | > k+b$ thus $k+b$ divides $P_i(k)$. So $R(k) = 0$. Considering all large primes $p$, there exist infinitely many zeros of $R(x)$. Thus $R \equiv 0$ and thus $ak+b \mid P_i(x)$ completing the induction hypothesis when $i > 1$. If $i =1$ then let $P_1(x) = rx+s$. Now by the same argument $k+b$ and $rk+s$ are both perfect powers of $p$. If $|rk+s| \geq |k+b|$ for all large $k$ then the same argument shows that $k+b$ divides $rk+s$. Suppose that $|k+b| \geq |rk+s|$ for all large $k$. Then the same argument shows that $rk+s$ divides $k+b$. If $|r| > 1$ then the former holds ($|rk+s| \geq | k +b|$ for large $k$). Thus $|r| = 1$. If $r =1$ then $k+s \mid k + b \implies k +s \mid b-s$. Letting $k$ large shows $b=s$. If $r = -1$ then $-k+s$ divides $k+b$ and so $-k+s$ divides $b+s$, and letting $k$ large gives $b=-s$. Thus in all cases we get that $P(x) = z(x+b)^d$ where $d$ is degree of $P$. Now to show that $z = \pm 1$, suppose for the sake of contradiction that $z$ has a prime divisor $p$. Then let $n = q \neq p$. Thus $p \mid z \mid q^m$, a contradiction! So $z = \pm 1$. It remains to show that $d$ is a divisor of $m$. Again let $p$ be a prime and let $n = p$. Then $|(k+b)^d|$ is a power of prime $p$ , thus $|k+b|$ is also a power of $p$. Letting $|k+b| = p^{\ell} \implies p^m = P(x) = p^{d \ell}$ (As $p^m>0$ we need not care about sign here). Thus $d$ divides $m$. Now if $d$ is even and $z = -1$ then $P \leq 0$ always, but its equal to positive integers too (Set $n = 1$ for example). So $z = 1$. Thus $P(x) = (x+b)^d$ if $d$ is even. Note that $(x+b)^d = (-1)^d(x+b)^d = (-x-b)^d = (-x+(-b))^d$. If $d$ is odd then $z = \pm 1$ is fine: $P(x) = \pm(x+b)^d = (\pm x + (\pm b))^d$ Thus we can say that the general solution is $P(x) = (\pm x + b)^d$ where $d$ is a positive divisor of $m$ , and $b$ is any arbitrary integer.

The answer is $P(x)=(\pm x -k)^\alpha$ where $k \in \mathbb{Z}$ and $\alpha \in \mathbb{N}$ where $\alpha$ divides $m$. Note that there exists $k$ where $P(k)=0^m=0$. So, wlog, shift $P$ so that $P(0)=0$. Thus, we see that $d$ divides $P(d)$ for all positive integers $d$. Note that for any prime $q$ there exists an $a$ for which $P(a)=q^m$ but recall that $a$ divides $P(a)$. So, it must follow that $a = \pm q^\ell$ for some $0 \leq \ell \leq m$. Thus, by infinite PHP, there exists a positive integer $\alpha \leq m$ and an infinite sequence of primes $q_1,q_2, \ldots$ for which either $P(q_i^\alpha)=q_i^m$ or $P(-q_i^\alpha)=q_i^m$. Assume wlog that $P(q_i^\alpha)=q_i^m$ Claim: if $P$ has degree $t$ then $\alpha t=m$ Let $Q(x)=P(x^\alpha)$. Note that $Q(a)=a^m$ has infinite solutions $a \in \mathbb{R}$, so it follows that $Q(x)=x^m$ so the degree of $Q$ is both $m$ and $\alpha t$ as desired. $\square$ Thus, since $\alpha t = m$ it follows that $\alpha$ divides $m$. Thus, undoing all of the wlogs, we are left with $P(x)=(\pm x - k)^\alpha$ as desired.

Letting $n=0$ we see $P(k_0)=0$ for some integer $k_0$. Note if $P(x)$ works, then $P(x+c)$ works for any integer $c$, so $Q(x)=P(x+k_0)$ works. Note $Q(0)=P(k_0)=0$. Hence, $x\mid Q(x)$. Claim: If we can write $Q(x)=x^\ell R(x)$ for a polynomial $R$ with integer coefficients an integer $\ell\ge 1$, then $Q(x)=\pm x^\ell$ (both may not work) or we can write $Q(x)=x^{\ell+1} R_1(x)$ for a polynomial $R_1$ with integer coefficients. Proof. Consider a prime $p$. Note that there exists $k$ such that $k^\ell R(k)=Q(k)=p^m$. Hence, $k\mid p^m$ so let $k=\pm p^t$. Then, $R(p^t)=\pm p^{m-\ell t}$. Letting $R(x)=a_sx^x+\dots +a_1 x+a_0$, we see \[a_s p^{ts}+a_{s-1}p^{t(s-1)}+\dots+p^ta_1+a_0\]Hence, we must have one or more of the following true: (i) $t=0$ (ii) $m=\ell t$ (iii) $p\mid a_0$. Varying $p$, we see (i) is true at most once as it implies $Q(1)=p^m$, which occurs for at most one $p$. Suppose $p\mid a_0$ is true finitely many times as $p$ varies. Then, $m=\ell t$ infinity many tries; that is, $R(p^t)=\pm 1$ infinity many times. Hence, either $R(x)-1$ or $R(x)+1$ has infinite roots so $R(x)=\pm 1$ so $Q(x)=\pm x^\ell$. $\blacksquare$ Let $\deg Q=d$. We claim by induction that for positive integers $z\le d$, we can write $Q(x)=x^zR_z(x)$ where $R_z$ is a polynomial with integer coefficients. For the base case $z=1$, we proved earlier that $x\mid Q(x)$. For the inductive step, if $z=y$ where $y+1\le d$ holds, by our claim $Q(x)=x^{y+1}R_{y+1}(x)$ or $Z(x)=\pm x^y$. The latter is false by degree comparison. Hence, our induction is complete so we can let $Z(x)=x^dR_d(x)$. Applying our claim, we have $Q(x)=\pm x^d$ or $Q(x)=x^{d+1}R_{d+1}(x)$. Again, the latter case is false by degrees. Suppose FTSOC that $d\mid m$. Then, letting $n=2$ we have $\pm k^d=2^m$ for some $k$. Note $k=\pm 2^a$ so $\pm 2^{ad}=2^m$ so $ad=m$, contradiction. Hence, $Q(x)=\pm x^d$ where $d\mid m$. Note if $d$ is odd both plus and minus work but if $d$ is even only plus works (or else $Q$ can't cover positive values). Hence, $Q(x)=(\pm x)^d$ so $P(x)=(\pm x+c)^d$. This works if we let $x=n^{m/d}\mp c$. $\square$

We claim that the only solutions are polynomials of the form $P(x)=(u-x)^{m/t}$ or $P(x)=(x-u)^{m/t}$, with $u$ an arbitrary integer and $t$ a positive divisor of $m$. The problem naturally splits into two parts. Part 1: All these polynomials work. Indeed, for $P(x)=(u-x)^{m/t}$ we may take $k=u-n^t$, and for $P(x)=(x-u)^{m/t}$ we may take $x=u+n^t$. Part 2: All polynomials that work are of this form. For $n=0$ in the given condition, there exists a $u$ such that $P(u)=0$. Now, for any prime $p$, let $p'$ be (one of) the corresponding integer such that $P(p')=p^m$. Then, $p'-u \mid P(p')-P(u)=p^m,$ hence $p'-u=\pm p^t$ for some $t \leq m$. Therefore, there exists an $\epsilon \in \{-1, 1 \}$ and an integer $t \leq m$, such that $p'+\epsilon p^t=u$ for infinitely many primes $p$. Therefore, $P(u-\epsilon p^t)=p^m$ for infinitely many $p$, which implies that $P(u-\epsilon x^t)=x^m$ for all $x$. Comparing the degrees of the two polynomials implies that $t \mid m$. If $\epsilon=1$, then $P(u-x^t)=x^m$ for all $x$, which implies that $P(x)=(u-x)^{m/t}$ for infinitely many $x$, and so $P(x)=(u-x)^{m/t}$ for all $x$. If $\epsilon=-1,$ then $P(u+x^t)=x^m$ for all $x$, and we similarly obtain that $P(x)=(x-u)^{m/t}$ for all $x$.

Let $f:Z->Z$ such that $P(f(n))=n^m$ then: $f(x)-f(y)|P(f(x))-P(f(y))=x^m-y^m$ Take now $y=0$ and $x=r=prime$ we get that $f(r)-c|r^m\Rightarrow f(r)=\pm r^d +c$ where $f(0)=c$. So since $d=0,1,2,3,..m$ there will be infinity primes which will have the same $d$ then we have: $P(a*r^d+c)=r^m$ for infinity primes which means that $P(a*x^d+c)=x^m$ for all $x$ (becayse if we let $R(x)=P(a*r^d+c)-r^m$ then it has infinity roots so $R(x)=0$ )with $a=1,-1$ Let now $P(x)=(x-c)^dQ(x)$ with $Q(c)\neq 0$ then we have: $x^m=P(a*x^b-c)=a^dx^{bd}Q(ax^b-c)\Rightarrow x^{m-bd}=a^dQ(ax^b-c)$ (1) If $m-bd\geqslant 1$ then for $x=0$ we have $Q(c)=0$ contradiction Obvioysly $m-bd\geqslant 0$ otherwise $deg(Q(x))$ will be negative wrong So $m=bd$ and (1) became $1=a^d*Q(ax^b-c)$ so $Q(ax^b-c)=+-1$ which gives $P(x)=+-(x-c)^d$ we have to pay a little attention to the parity of $d$ because for an even number it gives only positive or only negative. Esily we get the sollution: If $m=even=bd$ then $P(x)=+-(x-c)^d$ if $d=odd$ and $P(x)=+(x-c)^d$ if $d=even$ If $m=odd=bd$ then $P(x)=+-(x-c)^d$.

just 1 idea: let $P(f(x))=x$ then $f(x)-f(y) \mid x^m - y^m$.. if $m$ is odd then $f$ has a solution by https://artofproblemsolving.com/community/c6h488541p2737651 then it is easy to get $P(x)$ but if $m$ is not odd then we cannot use this solution

Anyone want to post their density solution? I know you're out there

Well, I'm finally getting to latexing my elmo solutions now... I claim the only solution(s) is: $P(x)=(\pm 1)^d \times (x+c)^d$ where $d$ is any natural number that divides $m$ and $c$ is an arbitrary integer. Clearly if $P(x)$ works so does $P(x+c)$ so WLOG assume $P(0)=0$. Also note that $P(\infty) \to -\infty$ implies $P(- \infty) \to \infty$ so WLOG assume $P(x)$ has a positive leading coefficient. Let $P(k_n)=n^m$. Let $\mathbb{P}$ be the set of primes. And now as we know $a-b \mid P(a)-P(b)$, so $P(k_p) \mid p^m \ \forall \ p \in \mathbb{P}$, but since primes are cool this implies that $P(k_p)=p^{t_p}$ for some $t_p \in [1,2 \cdots m]$ for all $p$. And now here is the main step, since primes are infinite, and $t_p$ can be zero at max once (because $P(1)$ can only take one value), this implies that there exists an infinite subset $\mathbb{Q}$ of $\mathbb{P}$ such that all the $t_q$ ($q \in \mathbb{Q})$ share some common value $t \in [1,2 \cdots m]$ And now our work is basically done, let $P(x)= \sum_{i=0}^d a_i x^i$. And now think only in terms of large enough $q \in \mathbb{Q}$. Since we have established that $P(q^t)=q^m$, $q^{td-1} < \sum_{i=0}^d a_i q^{it} < q^{td+1}$ but the middle thing is $P(q^t)=q^m$, so $q^m$ is a power of $q$ between $q^{td-1}$ and $q^{td+1}$ so we must have $m=td$ And so now we have $\sum_{i=0}^{d-1} a_i q^it + (a_d -1)q^td=0$ for all large enough $q$ and the only polynomial that is zero infinitely often is the zero polynomial so this implies $P(x)=x^d$ for some $d \mid m$ (because $td=m$) and the rest of the solution set comes from our initial two assumptions. Really cool problem What is submitted is attached below

IAmTheHazard wrote: Anyone want to post their density solution? I know you're out there I really want to see this, could you post it yourself please?

For any positive \(d\mid n\), the polynomials \(P(x)=(x+a)^d\) and \(P(x)=(-x+a)^d\) work. We show they are the only solutions. First, there exists \(k_0\) so that \(P(k_0)=0^m\). Instead consider the polynomial \(Q(x)=P(x-k_0)\), which has 0 as a root and but still contains every \(m\)th power in its range. We will show that \(Q(x)\) is of the form either \(x^d\) or \((-x)^d\) for some \(d\mid n\). For each prime \(p\), there is some \(k_p\) with \(Q(k_p)=p^m\). Since 0 is a root of \(Q\), we have \(x\mid Q(x)\) for every \(x\). In particular, \(k_p\mid P(k_p)=p^m\). This implies that \[k_p\in\{1,p,p^2,\ldots,p^m,-1,-p,-p^2,\ldots,-p^m\}\quad\text{for all }p.\] By the Pigeonhole principle, one of the following must occur: There is some \(0\le r\le m\) such that \(k_p=p^r\) for infinitely many \(p\). In particular, \(Q(x^r)=x^m\) infinitely often, implying it holds for all real \(x\), so \(Q(x)=x^{m/r}\) for all \(x\). There is some \(0\le r\le m\) such that \(k_p=-p^r\) for infinitely many \(p\). In particular, \(Q(-x^r)=x^m\) infinitely often, implying it holds for all real \(x\), so \(Q(x)=(-x)^{m/r}\) for all \(x\). This completes the proof.

The answers are $P(x)=(\pm x-k)^n$ for any integer $k$ and $n\mid n$. These work as $P\left(\pm x^{\frac mn} +k\right)=x^m.$ Notice that if $P(x)$ is a solution, so is $P(\pm x +k)$ for integer $k$. There exists a $j$ with $p(j)=0^m=0,$ thus WLOG shift $P$ so $P(0)=0.$

we see $P_1$ is a polynomial with infinitely many zeroes so $P_1(x)=0$ and $P(x)^y=\pm x^m$ or $P(x)=\pm x^{\frac my}$ for $y\mid m$. Thus $P(x)=\pm x^j$ for $j\mid m$, and we get the other results by shifting $P(x)$ to $P(\pm x+k)$.

Seemingly similar though very different problem appeared on Kazakhstan National Olympiad $2021$. Apparently, if $n$ is a positive integer and $P(x) \in R[x]$ is such that for any positive integer $k$, there exists positive integer $l$ such that $P(l) = m^n$, then $P(x) = (ax + b)^k$ for some real numbers $a, b$ and positive integer $k$.

An alternative solution. Take $P(X)=A.R_1(X)^{\alpha _1}...R_s(X)^{\alpha _s}$ where $R_i \in \mathbb Z[X]$ is irreducible over $Z[X]$ for $i=1,...,s$; $A$ is an integer constant; $Q \in \mathbb Z[X]$. Since $(R_i,R_j)=1$, there exist $T_{ij}, T_{ji} \in \mathbb Z[X]$ such that $R_i(X).T_{ij}(X)+R_j(X).T_{ji}(X)=c_{ij}$ where $c \in \mathbb Z^+$. Take a prime $p$ s.t. it is larger than all $c_{ij}$'s and for an $r$ such that at least one of $R_i(r)$'s is $\pm 1$, $p^m>P(r)$. Hence, if $s \geq 2$, then we have contradiction ($p|R_i(k)$ for any $i$.). Then $s=0,1$. If $s=0$, then $P(X)=A$, but this results in contradiction obviously. If $s=1$, we have $P(X)=A.R(X)^{\alpha}$. By taking a prime $p>|A|$, we get that $A=\pm 1$. We may suppose that $A=1$ (if $\alpha$ is even, it is obvious; otherwise, multiply $R$ by $-1$). Using the methods mentioned above, we conclude that $P(x)=(\pm x +c)^\alpha$ for an $\alpha | m$ and an integer $c$.

We claim that the only sols are $(\pm x+c)^d$ with $c$ an integer and $d$ a positive divisor of $m$ We know that there exists a number whose image with $P$ is $0$, shift $P$ so that it's $0$ and replace $P(x)$ by $P(-x)$ if necessary so that $P$ is infinitely positive, take a prime $p$, then if $P(k)=p^m$ then $k|P(k)-P(0)=p^m$ so $k$ is a power of $p$ which we set to be $p^k,$ clearly for large enough $p$ we must have $k\le m$ so by infinite PHP(since there is a finite number of $k$s) we get a value of $k$ which we call $d$ that's repeated for infinitely many primes $p$ thus $P(p^d)=p^m$ for infinitely many primes $p$ implying $P(x)=x^d$ for all $x,$ checking we find that $d\mid m$ which gives us our sols

This can be generalized to having this hold for a set of any integers $n_1 < n_2 < \dots$ such that $\frac{n_{N+k}}{n_N}$ approaches $1$ (sub-exponential) that are dense in residues and contain infinitely many $d$th powers for each $d$. Let $P$ have degree $d$. Note that $P(k)$ contains terms of the form $n^{md}$ for each $d$. Define $x_i = k_i$ for $x_1, \dots, x_N$ such that $P(x_i) = (n_{N+i})^{md}$ for arbitrarily large $N$ such that $\frac{n_{N+n}}{n_{N+1}} < 2^{-1434md}$. We can verify that $\frac{1}{2} < \frac{P(x_i)}{P(x_i)} < 2$ and that $\frac{P(x_i)}{P(x_j)}$ is a $d$-th power of a rational. As such, by generalized Shortlist 2016 N8 it follows that $P(x) = c (ax + b)^d$ for integers $a, b$ and rational $c$. It is well-known that $n_i$ is divisible by infinitely many primes, so taking large prime $p$ such that $p$ doesn't appear in the factorization of $c$, it must follow that $d \mid m$, and that $c$ is a $d$th power. It thus follows that we can re-express $P(x) = (ax + b)^d$ due to being integral. By density it follows that $a = \pm 1$.

There exists some $k$ for which $P(k)=0$. Then, shift by $k$ so that we have $P(0)=0$. So, we have $a\mid P(a)$ for every $a$. So, for every prime $p$ we have $a\mid P(a)=p^{m}$, which means $a=p^l$ with $0\leq l\leq m$. Since there are infinitely many primes, one exponent $l_0$ occurs infinitely many times, i.e. there are infinitely primes for which $P(p^l) = p^m$. Let $Q(x) = P(x^l)$. Then, there are infinitely many solutions to $Q(x) = x^m$, which means $Q(x)$ and $x^m$ always agree. So, $Q(x) = x^m$ for every real $x$. Hence, $\frac ml$ is an integer and $P(x) = x^{\frac ml}$ or $P(x) = -x^{\frac ml}$ (if $\frac ml$ is odd.) Re-shifting $x$ in $P$, we see that all the valid solutions are \[P(x)\in \left\{(x-k)^{\frac ml}, \ \ \ \text{and} \ \ \ (k-x)^{\frac ml} \ \ \ \text{given } l\mid m\text{ and }k\in\mathbb{N}\right\}\]Indeed, these solutions work.

Claim: If $P(x)$ is a solution then so is $P(\pm x+k)$. Proof: There exists a $c$ such that $P(c)=0^m=0$, now shift $P$ such that $P(0)=0$. Let $a_p$ be a number such that $P(a_p)=p^m$, since $P(0)=0$ we get $a_p\mid p^m$. So possible values of $a_p$ are $\{\pm1,\pm p,\pm p^2, \dots, \pm p^m\}$. By Pigeonhole Principle $\exists$ $0\leq t\leq m$ such that $a_p=\pm p^t$ for infinitely many $t$ and $P_1(x)=P(x)^t+\pm x^m$, we also have $P_1(x)=0$. So $P(x)^t=\pm x^m$ . We finally get our desired answers to be $(\pm x+k)^i, i \mid m$ by shifting $P(x) \to P(\pm x+k)$.

After writing down the solution, I realised that this one is really similar to sdninajanlari's solution at #17. How couldn't I know this? Answer is $P(x)=(\pm x+b)^r$ where $b$ is any integer and $r$ is a positive divisor of $m$. Lemma: If $R(x)$ and $S(x)$ are coprime polynomials in integers, then there exists a constant $D$ with $(R(x),S(x))\leq D$. Proof: By Bezout, there exists $A,B$ such that $A(x)R(x)+B(x)S(x)=C$ where $C$ is a constant. Hence $p^k|R(x),S(x)$ implies $p^k|C$ which is bounded.$\square$ Let $P(x)=Q_1(x)^{\alpha_1}\dots Q_l^{\alpha_l}(x)$ with $Q_i(x),Q_j(x)$ are coprime. By the lemma, we see that $(Q_i(x),Q_j(x))\leq D$ for some constant $C$ for each $1\leq i\leq j\leq l$. By the condition, there exists some $k$ for a prime $p\gg D$ where $Q_1(k)^{\alpha_1}\dots Q_l^{\alpha_l}(k)=P(k)=p^m$ and since $p$ is sufficiently large, $p$ cannot divide both $Q_i(k)$ and $Q_j(k)$ at the same time thus, $l-1$ polynomials among $Q_i'$s must be constant (because $l-1$ of them are $\pm 1$ infinitely many times) which yields $P(x)=c.Q(x)^{\alpha}$ and $|c|=1$ since $c|n$ for each positive integer $n$. The polynomial $Q(x)$ can be divisible by each prime so by Chebotarev we get that $Q$ is linear. Let $Q(x)=ax+b$ and $P(x)=\pm (ax+b)^{\alpha}$. We have $\pm (ax+b)^{\alpha}=p^m$ for a prime and $ax+b=p^t$ for some $t$. This gives $t.\alpha=m$ hence $\alpha|m$. Let $m=\alpha .r$ so there exists $x$ such that $\pm (ax+b)=n^r$. We see that $b=0$ yields $a=\pm 1$ which is a solution. Suppose that $b\neq 0$. We see that $a\neq 0$. If $|a|>1$, then multiples of $a$ cannot be in the image of $P$ which contradicts with the condition. So $a=\pm 1$. We get the desired conclusion.$\blacksquare$