We have your learning goals covered with Spring and Summer courses available. Enroll today!

G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21


Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Friday, Apr 11 - Jun 27
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Monday, Mar 24 - Jun 16
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
concurrency wanted, starting with a 45-135/2 - 135/2 triangle
parmenides51   2
N a few seconds ago by GioOrnikapa
Source: 2020 Balkan MO shortlist G5
Let $ABC$ be an isosceles triangle with $AB = AC$ and $\angle A = 45^o$. Its circumcircle $(c)$ has center $O, M$ is the midpoint of $BC$ and $D$ is the foot of the perpendicular from $C$ to $AB$. With center $C$ and radius $CD$ we draw a circle which internally intersects $AC$ at the point $F$ and the circle $(c)$ at the points $Z$ and $E$, such that $Z$ lies on the small arc $BC$ and $E$ on the small arc $AC$. Prove that the lines $ZE$, $CO$, $FM$ are concurrent.

Brazitikos Silouanos, Greece
2 replies
parmenides51
Sep 14, 2021
GioOrnikapa
a few seconds ago
Another SL problem about fibonacci numbers :3
MathLuis   13
N 5 minutes ago by hgomamogh
Source: ISL 2020 C4
The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$.

Proposed by Croatia
13 replies
MathLuis
Jul 20, 2021
hgomamogh
5 minutes ago
USAMO 1983 Problem 2 - Roots of Quintic
Binomial-theorem   28
N 41 minutes ago by Marcus_Zhang
Source: USAMO 1983 Problem 2
Prove that the roots of\[x^5 + ax^4 + bx^3 + cx^2 + dx + e = 0\] cannot all be real if $2a^2 < 5b$.
28 replies
Binomial-theorem
Aug 16, 2011
Marcus_Zhang
41 minutes ago
Find the period
Anto0110   0
44 minutes ago
Let $a_1, a_2, ..., a_k, ...$ be a sequence that consists of an initial block of $p$ positive distinct integers that then repeat periodically. This means that $\{a_1, a_2, \dots, a_p\}$ are $p$ distinct positive integers and $a_{n+p}=a_n$ for every positive integer $n$. The terms of the sequence are not known and the goal is to find the period $p$. To do this, at each move it possible to reveal the value of a term of the sequence at your choice.
If $p$ is one of the first $k$ prime numbers, find for which values of $k$ there exist a strategy that allows to find $p$ revealing at most $8$ terms of the sequence.
0 replies
Anto0110
44 minutes ago
0 replies
Diophantine equation
PaperMath   9
N an hour ago by gaussiemann144
Find the $5$ smallest positive solutions of $x$ that has an integer $k$ that satisfies $x^2=3k^2+4$
9 replies
PaperMath
Mar 12, 2025
gaussiemann144
an hour ago
How many ordered pairs of numbers can we find?
BR1F1SZ   2
N an hour ago by BR1F1SZ
Source: 2024 Argentina TST P6
Given $2024$ non-negative real numbers $x_1, x_2, \dots, x_{2024}$ that satisfy $x_1 + x_2 + \cdots + x_{2024} = 1$, determine the maximum possible number of ordered pairs $(i, j)$ such that
\[
x_i^2 + x_j \geqslant \frac{1}{2023}.
\]
2 replies
BR1F1SZ
Jan 25, 2025
BR1F1SZ
an hour ago
IMO 2009, Problem 5
orl   87
N 2 hours ago by asdf334
Source: IMO 2009, Problem 5
Determine all functions $ f$ from the set of positive integers to the set of positive integers such that, for all positive integers $ a$ and $ b$, there exists a non-degenerate triangle with sides of lengths
\[ a, f(b) \text{ and } f(b + f(a) - 1).\]
(A triangle is non-degenerate if its vertices are not collinear.)

Proposed by Bruno Le Floch, France
87 replies
orl
Jul 16, 2009
asdf334
2 hours ago
1978 USAMO #1
Mrdavid445   54
N 2 hours ago by Marcus_Zhang
Given that $a,b,c,d,e$ are real numbers such that

$a+b+c+d+e=8$,
$a^2+b^2+c^2+d^2+e^2=16$.

Determine the maximum value of $e$.
54 replies
Mrdavid445
Aug 16, 2011
Marcus_Zhang
2 hours ago
The return of a legend inequality
giangtruong13   4
N 2 hours ago by Double07
Source: Legacy
Given that $0<a,b,c,d<1$.Prove that: $$ (1-a)(1-b)(1-c)(1-d) > 1-a-b-c-d $$
4 replies
giangtruong13
4 hours ago
Double07
2 hours ago
degree of f=2^k
Sayan   15
N 2 hours ago by Gejabsk
Source: ISI 2012 #8
Let $S = \{1,2,3,\ldots,n\}$. Consider a function $f\colon S\to S$. A subset $D$ of $S$ is said to be invariant if for all $x\in D$ we have $f(x)\in D$. The empty set and $S$ are also considered as invariant subsets. By $\deg (f)$ we define the number of invariant subsets $D$ of $S$ for the function $f$.

i) Show that there exists a function $f\colon S\to S$ such that $\deg (f)=2$.

ii) Show that for every $1\leq k\leq n$ there exists a function $f\colon S\to S$ such that $\deg (f)=2^{k}$.
15 replies
Sayan
May 13, 2012
Gejabsk
2 hours ago
Local-global with Fibonacci numbers
MarkBcc168   26
N 2 hours ago by pi271828
Source: ELMO 2020 P2
Define the Fibonacci numbers by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n\geq 3$. Let $k$ be a positive integer. Suppose that for every positive integer $m$ there exists a positive integer $n$ such that $m \mid F_n-k$. Must $k$ be a Fibonacci number?

Proposed by Fedir Yudin.
26 replies
MarkBcc168
Jul 28, 2020
pi271828
2 hours ago
Cauchy functional equations
syk0526   10
N 3 hours ago by imagien_bad
Source: FKMO 2013 #2
Find all functions $ f : \mathbb{R}\to\mathbb{R}$ satisfying following conditions.
(a) $ f(x) \ge 0 $ for all $ x \in \mathbb{R} $.
(b) For $ a, b, c, d \in \mathbb{R} $ with $ ab + bc + cd = 0 $, equality $ f(a-b) + f(c-d) = f(a) + f(b+c) + f(d) $ holds.
10 replies
syk0526
Mar 24, 2013
imagien_bad
3 hours ago
Three circles are concurrent
Twoisaprime   21
N 3 hours ago by L13832
Source: RMM 2025 P5
Let triangle $ABC$ be an acute triangle with $AB<AC$ and let $H$ and $O$ be its orthocenter and circumcenter, respectively. Let $\Gamma$ be the circle $BOC$. The line $AO$ and the circle of radius $AO$ centered at $A$ cross $\Gamma$ at $A’$ and $F$, respectively. Prove that $\Gamma$ , the circle on diameter $AA’$ and circle $AFH$ are concurrent.
Proposed by Romania, Radu-Andrew Lecoiu
21 replies
Twoisaprime
Feb 13, 2025
L13832
3 hours ago
IMO Shortlist 2011, Algebra 3
orl   45
N 3 hours ago by Ilikeminecraft
Source: IMO Shortlist 2011, Algebra 3
Determine all pairs $(f,g)$ of functions from the set of real numbers to itself that satisfy \[g(f(x+y)) = f(x) + (2x + y)g(y)\] for all real numbers $x$ and $y$.

Proposed by Japan
45 replies
orl
Jul 11, 2012
Ilikeminecraft
3 hours ago
Polynomial produces perfect powers
TheUltimate123   21
N Mar 15, 2025 by pi271828
Source: ELMO 2023/1
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
21 replies
TheUltimate123
Jun 26, 2023
pi271828
Mar 15, 2025
Polynomial produces perfect powers
G H J
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.
TheUltimate123
1739 posts
#1 • 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
#2 • 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.
blackbluecar
302 posts
#3 • 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.
Mogmog8
1080 posts
#4 • 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.
Orestis_Lignos
555 posts
#5 • 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.
P2nisic
406 posts
#6 • 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.
MrOreoJuice
594 posts
#7 • 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
#9 • 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.
VicKmath7
1385 posts
#10 • 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.
IAmTheHazard
5000 posts
#11 • 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:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
a_n
162 posts
#12 • 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:
p1.pdf (102kb)
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.
a_n
162 posts
#13 • 1 Y
Y by ImSh95
IAmTheHazard wrote:
Anyone want to post their density solution? I know you're out there :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.
TheUltimate123
1739 posts
#14 • 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.
GrantStar
812 posts
#15 • 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.
GoldenBoy03
22 posts
#16 • 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.
sdninajanlari
25 posts
#17 • 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.
cosmos1999
5 posts
#18
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.
TheHazard
93 posts
#19 • 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.
Pyramix
419 posts
#20 • 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.
L13832
250 posts
#21
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.
bin_sherlo
661 posts
#22 • 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? :D
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.
pi271828
3363 posts
#23
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
=
a