Polynomial produces perfect powers

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Polynomial produces perfect powers

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ELMO 2023/1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1739 posts

#1 h Jun 26, 2023, 5:14 AM • 4 Y

Y by GeoKing, ImSh95, Stuart111, Rounak_iitr

Let $m$ be a positive integer. Find, in terms of $m$ , all polynomials $P(x)$ with integer coefficients such that for every integer $n$ , there exists an integer $k$ such that $P(k)=n^m$ .

Proposed by Raymond Feng

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicNumberTheory

250 posts

EpicNumberTheory

#2 h Jun 26, 2023, 5:58 AM • 3 Y

Y by Nuterrow, GeoKing, ImSh95

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.

This post has been edited 1 time. Last edited by EpicNumberTheory, Jun 26, 2023, 5:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

302 posts

#3 h Jun 26, 2023, 6:07 AM • 8 Y

Y by Nuterrow, PRMOisTheHardestExam, LoloChen, ImSh95, GeoKing, Rounak_iitr, XbenX, Math_legendno12

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.

This post has been edited 4 times. Last edited by blackbluecar, Feb 29, 2024, 1:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#4 h Jun 26, 2023, 6:24 AM • 2 Y

Y by centslordm, ImSh95

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

555 posts

#5 h Jun 26, 2023, 6:38 AM • 1 Y

Y by ImSh95

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

406 posts

#6 h Jun 26, 2023, 7:03 AM • 2 Y

Y by GeoKing, ImSh95

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

594 posts

#7 h Jun 26, 2023, 7:59 AM • 5 Y

Y by GeoKing, PRMOisTheHardestExam, SatisfiedMagma, ImSh95, EndipifromBMT

Answer
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PRMOisTheHardestExam

409 posts

PRMOisTheHardestExam

#9 h Jun 26, 2023, 2:21 PM • 1 Y

Y by ImSh95

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1385 posts

#10 h Jun 26, 2023, 4:01 PM • 1 Y

Y by ImSh95

Algebraic solution

This post has been edited 9 times. Last edited by VicKmath7, Jul 19, 2023, 8:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5000 posts

#11 h Jun 27, 2023, 3:53 AM • 8 Y

Y by GeoKing, PRMOisTheHardestExam, ImSh95, Aryan-23, centslordm, megarnie, khina, ohiorizzler1434

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

:ninja:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

162 posts

a_n

#12 h Jun 30, 2023, 1:19 PM • 1 Y

Y by ImSh95

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

Attachments:

This post has been edited 1 time. Last edited by a_n, Jun 30, 2023, 1:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

162 posts

a_n

#13 h Jun 30, 2023, 1:20 PM • 1 Y

Y by ImSh95

IAmTheHazard wrote:

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

:ninja:

I really want to see this, could you post it yourself please?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1739 posts

#14 h Jun 30, 2023, 9:52 PM • 3 Y

Y by PRMOisTheHardestExam, Rounak_iitr, ike.chen

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

813 posts

#15 h Jul 18, 2023, 4:23 AM • 2 Y

Y by PRMOisTheHardestExam, ike.chen

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.$

Now turn this into NT! For each prime $p$ , let $x_p$ be a number with $P(x_p)=p^m.$ There might be multiple $\ell$ with $P(\ell)=x^m$ so choose the one with the smallest absolute value. Then, notice that $x_p=x_p-0\mid P(x_p)-P(0)=p^m$ so thus $x_p=\pm 1, \pm p, \pm p^2, \dots, \pm p^m$ for each prime. Then, let $f(p)=v_p(x_p)=1,2,\dots, m.$ As there are infinitely many primes but finitely many choices of $f(p),$ be pigeonhole f(p) takes the same value $y$ infinitely many times. Considering $p_1(x)=P(x)^y\pm x^m$ , 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)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

22 posts

#16 h Jul 24, 2023, 7:46 PM • 1 Y

Y by PRMOisTheHardestExam

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$ .

This post has been edited 1 time. Last edited by GoldenBoy03, Jul 24, 2023, 7:46 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

25 posts

#17 h Nov 25, 2023, 3:46 PM • 1 Y

Y by bin_sherlo

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$ .

This post has been edited 1 time. Last edited by sdninajanlari, Nov 25, 2023, 3:48 PM
Reason: typo again

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5 posts

#18 h Jan 19, 2024, 5:59 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

93 posts

#19 h Jan 19, 2024, 6:44 PM • 1 Y

Y by PRMOisTheHardestExam

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$ .

This post has been edited 1 time. Last edited by TheHazard, Jan 19, 2024, 6:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

419 posts

#20 h Apr 3, 2024, 1:11 PM • 1 Y

Y by PRMOisTheHardestExam

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

250 posts

L13832

#21 h Sep 3, 2024, 4:07 AM

Y by

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)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

662 posts

#22 h Dec 1, 2024, 12:00 PM • 1 Y

Y by tiny_brain123

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3363 posts

#23 h Mar 15, 2025, 8:18 PM

Y by

The answer is $P(x) = (x+k)^d$ and $P(x) = (-x+k)^d$ where $d \mid m$ , which clearly works. Note that from setting $n = 0$ , $P(x)$ must have an integer root, so we shift such that $P(0) = 0$ . The following claim finishes the problem.

Claim: $P(x)$ must be of the form $x^{\ell}$ or $-x^{\ell}$ where $\ell \mid m$ .

Proof. Set $n$ to be a prime $p$ , such that $P(a_p) = p^m$ . Clearly this implies $a_p \mid p^m$ , or in other words $\begin{align*} a_p \in \{-p^{m}, -p^{m-1}, \dots, p^{m-1}, p^{m} \} = S\end{align*}$ There are infinitely many primes and $|S|$ is finite, so by pigeonhole, there must be an integer $\ell \le m$ and integer $k \in \{0, 1\}$ such that $a_p = (-1)^k \cdot p^{\ell}$ for infinitely many primes $p$ . This implies there are infinitely many $x$ such that $P(x) = (-1)^k \cdot x^{m/ \ell}$ . The polynomial $Q(x) = P(x)^\ell - (-1)^{k \ell} x^m$ therefore has infinitely many roots, implying $P(x)^{\ell} = (-1)^{k\ell} x^m$ , which means $\ell \mid m$ . The claim readily follows. $\square$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a