Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/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
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
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, 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
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
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
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
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

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
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
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
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
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
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
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

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

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
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
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 2025
0 replies
Batman chases the Joker on a square board
Lukaluce   1
N 22 minutes ago by navier3072
Source: 2025 Junior Macedonian Mathematical Olympiad P1
Batman, Robin, and The Joker are in three of the vertex cells in a square $2025 \times 2025$ board, such that Batman and Robin are on the same diagonal (picture). In each round, first The Joker moves to an adjacent cell (having a common side), without exiting the board. Then in the same round Batman and Robin move to an adjacent cell. The Joker wins if he reaches the fourth "target" vertex cell (marked T). Batman and Robin win if they catch The Joker i.e. at least one of them is on the same cell as The Joker.

If in each move all three can see where the others moved, who has a winning strategy, The Joker, or Batman and Robin? Explain the answer.

Comment. Batman and Robin decide their common strategy at the beginning.

IMAGE
1 reply
Lukaluce
Yesterday at 3:23 PM
navier3072
22 minutes ago
Interesting inequalities
sqing   12
N 27 minutes ago by ytChen
Source: Own
Let $ a,b,c\geq 0 , (a+k )(b+c)=k+1.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{2k-3+2\sqrt{k+1}}{3k-1}$$Where $ k\geq \frac{2}{3}.$
Let $ a,b,c\geq 0 , (a+1)(b+c)=2.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq 2\sqrt{2}-1$$Let $ a,b,c\geq 0 , (a+3)(b+c)=4.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{7}{4}$$Let $ a,b,c\geq 0 , (3a+2)(b+c)= 5.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{2(2\sqrt{15}-5)}{3}$$
12 replies
sqing
May 10, 2025
ytChen
27 minutes ago
Foot from vertex to Euler line
cjquines0   31
N an hour ago by awesomeming327.
Source: 2016 IMO Shortlist G5
Let $D$ be the foot of perpendicular from $A$ to the Euler line (the line passing through the circumcentre and the orthocentre) of an acute scalene triangle $ABC$. A circle $\omega$ with centre $S$ passes through $A$ and $D$, and it intersects sides $AB$ and $AC$ at $X$ and $Y$ respectively. Let $P$ be the foot of altitude from $A$ to $BC$, and let $M$ be the midpoint of $BC$. Prove that the circumcentre of triangle $XSY$ is equidistant from $P$ and $M$.
31 replies
cjquines0
Jul 19, 2017
awesomeming327.
an hour ago
Integer polynomial commutes with sum of digits
cjquines0   43
N an hour ago by Ilikeminecraft
Source: 2016 IMO Shortlist N1
For any positive integer $k$, denote the sum of digits of $k$ in its decimal representation by $S(k)$. Find all polynomials $P(x)$ with integer coefficients such that for any positive integer $n \geq 2016$, the integer $P(n)$ is positive and $$S(P(n)) = P(S(n)).$$
Proposed by Warut Suksompong, Thailand
43 replies
cjquines0
Jul 19, 2017
Ilikeminecraft
an hour ago
No more topics!
Integer Coefficient Polynomial with order
MNJ2357   9
N Apr 5, 2025 by v_Enhance
Source: 2019 Korea Winter Program Practice Test 1 Problem 3
Find all polynomials $P(x)$ with integer coefficients such that for all positive number $n$ and prime $p$ satisfying $p\nmid nP(n)$, we have $ord_p(n)\ge ord_p(P(n))$.
9 replies
MNJ2357
Jan 12, 2019
v_Enhance
Apr 5, 2025
Integer Coefficient Polynomial with order
G H J
G H BBookmark kLocked kLocked NReply
Source: 2019 Korea Winter Program Practice Test 1 Problem 3
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MNJ2357
644 posts
#1 • 2 Y
Y by Superguy, Adventure10
Find all polynomials $P(x)$ with integer coefficients such that for all positive number $n$ and prime $p$ satisfying $p\nmid nP(n)$, we have $ord_p(n)\ge ord_p(P(n))$.
This post has been edited 1 time. Last edited by MNJ2357, Jan 12, 2019, 10:17 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
stroller
894 posts
#2 • 2 Y
Y by Adventure10, Mango247
Wrong, thanks to post below for pointing out :stretcher:
This post has been edited 3 times. Last edited by stroller, Jan 16, 2019, 2:00 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fattypiggy123
615 posts
#3 • 2 Y
Y by stroller, Adventure10
stroller wrote:

The given condition translates to $p | n- \omega_k \implies p | P(n)^k -1 $

Shouldn't this be $p \mid P(n)^m - 1$ for some $m \leq k$?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
stroller
894 posts
#4 • 1 Y
Y by Adventure10
fattypiggy123 wrote:
stroller wrote:

The given condition translates to $p | n- \omega_k \implies p | P(n)^k -1 $

Shouldn't this be $p \mid P(n)^m - 1$ for some $m \leq k$?

Sorry my mistake; I misread the problem as $\text{ord}_p(P(n))|\text{ord}_p(n)$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
stroller
894 posts
#5 • 2 Y
Y by Adventure10, Mango247
My fix for the error pointed out in post #3.

What I was most concerned about being incorrect
This post has been edited 1 time. Last edited by stroller, Jan 16, 2019, 1:55 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fattypiggy123
615 posts
#6 • 4 Y
Y by Kayak, stroller, Adventure10, Mango247
Yes your solution has a few points of contention, for instance $\omega_k$ starts off life as an element of $\mathbb{F}_p$ but somehow becomes an actual complex root of unity halfway through. All of this can be fixed/made rigorous by some algebraic number theory. I will post more on it when I am free.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fattypiggy123
615 posts
#7 • 7 Y
Y by Loppukilpailija, stroller, MNJ2357, Gaussian_cyber, Superguy, Adventure10, Mango247
The main idea to stroller's solution is to attempt to lift the local conditions, $P(u_p) \equiv v_p \pmod p$ where $u_p,v_p$ are integers satisfying $u_p^k , v_p^m \equiv 1 \pmod p$, into a global condition $p \mid P(x) - y$ for some numbers $x,y$ to deduce that $P(x) - y = 0$ since it cannot have infinitely many distinct prime factors. For instance if $k = m = 1$, then we can simply choose $x = y = 1$. The problem comes when $k$ and $m$ are larger than $2$ and one cannot find any integer $x$ such that $x^k \equiv 1 \pmod p$ for infinitely many primes $p$ where $x \not = 1$. As indicated in stroller's solution, we should bring in the complex primitive roots of unity $\omega_k$ and $\omega_m$. For simplicity, I will just assume $m = k$.

Now there is a natural place (but not the only one!) to do arithmetic with $\omega_k$. The field $\mathbb{Q}(\omega_k)$ is a number field and so its ring of integers is a Dedekind domain. When working beyond $\mathbb{Z}$, it is known that we cannot hope for unique factorization of integers to continue to hold. What one can achieve however is unique factorization into ideals, which is a property that Dedekind domains possess (and can also be taken as its defining property) and so makes Dedekind domains a nice place to do arithmetic in. In the case of $\mathbb{Q}(\omega_k)$, its ring of integers is simply $\mathbb{Z}[\omega_k]$, which is just sums of $\omega_k^i$ with $\mathbb{Z}$-coefficients.

For a prime $p$, let $\mathbb{F}_q$ be the smallest field extension of $\mathbb{F}_p$ where you have a primitive $k^{th}$ root of unity. This always exists if say $p \nmid k$. Then just like how in the usual integers $\mathbb{Z}$, we have the "reduction mod p" maps from $\mathbb{Z}$ to $\mathbb{F}_p$, there will exist reduction maps from $\mathbb{Z}[\omega_k]$ to $\mathbb{F}_q$ for each such $q$ where $\omega_k$ is sent to one of the primitive $k^{th}$ roots of unity in $\mathbb{F}_q$. When $p \nmid k$, the ideal $(p)$ in $\mathbb{Z}[\omega_k]$ factors as a product of distinct prime ideals $\mathfrak{p}_1 \cdots \mathfrak{p}_g$. These reduction maps then arise from reducing modulo $\mathfrak{p}_i$ instead of just mod $p$.

For example, if we work over the Gaussain integers $\mathbb{Z}[i]$ instead then we are looking at field extensions $\mathbb{F}_q$ where $x^2 = -1$ has a solution. For $p = 3$, there are no solutions within $\mathbb{F}_3$ itself and so we have to extend to $\mathbb{F}_9$, the field with $9$ elements. Correspondingly, the element/ideal $(3)$ is prime in $\mathbb{Z}[i]$ and so the map $\mathbb{Z}[i] \to \mathbb{F}_9$ arises from $a + bi \mapsto a \pmod 3 + b \pmod 3 i$. You can check that there are then $9$ elements just like $\mathbb{F}_9$. Howeverfor $p = 5$, within $\mathbb{F}_5$ there is already a solution to $x^2 = -1$ and so $\mathbb{F}_q = \mathbb{F}_5$. Our map $\mathbb{Z}[i] \to \mathbb{F}_5$ can't be just reducing mod $5$ then as that will give us $25$ elements instead. Instead one should factor $(5) = (2+i)(2-i)$ and then reduce mod $(2+i)$ or $(2-i)$. Since $x^2 + 1 = 0$ has two solutions in $\mathbb{F}_5$, there are two possible elements one can map $i$ to and each mod corresponds to one of them.

As a result, we can lift the local conditions to get for each $p \equiv 1 \pmod k$, there is one prime ideal factor $\mathfrak{p}$ of the ideal $(p)$ that divides $P(\omega_k) - \omega_k^m$ which implies that it must be $0$ by unique factorization of ideals.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MarkBcc168
1595 posts
#8 • 3 Y
Y by stroller, Gaussian_cyber, Adventure10
Here is alternative way to make stroller's solution rigorous, using elementary method. We will prove that $P(\omega_k)^{k!}=1$.

The key idea is to transfer from $\mathbb{Q}(\omega_k)$ to $\mathbb{Z}_p$ properly. However, the difficulty is $\omega_k$ is defined through roots of polynomials, which means we don't know the order of root. We will circumvent this issue by using symmetric polynomials instead.

Fix a positive integer $n$ and let $m=\varphi(n)$. Let $\omega_1, \omega_2, ...,\omega_m$ be primitive $n$-th root unity. By Newton's theorem on polynomial on symmetric polynomial, polynomial
$$Q(X) = (X-P(\omega_1))(X-P(\omega_2))...(X-P(\omega_m))$$has integer coefficients.

Fix a prime $p\equiv 1\pmod n$ and working on $\mathbb{F}_p[X]$. Let $a_1,a_2,...,a_m$ be all residues $\pmod p$ having order $n$. We claim that
Claim 1 : Let
$$Q^*(X) = (X-P(a_1))(X-P(a_2))...(X-P(a_m))$$then $Q^*(X) - Q(X)$ has all coefficients divisible by $p$.

Proof : Let $e_1, e_2,...,e_m$ be Elementary symmetric polynomials of $m$ variables. Then in $\mathbb{F}_p[X]$,
$$(X-a_1)(X-a_2)...(X-a_m) = \varPhi_n(X) = (X-\omega_1)(X-\omega_2)...(X-\omega_m)$$Thus comparing coefficients give $e_i(a_1,a_2,...,a_m) \equiv e_i(\omega_1,\omega_2,...,\omega_m) \pmod{p}$ for any $i=1,2,...,m$. (Recall that both numbers are integer!). Therefore, by Newton's theorem on symmetric polynomial,
$$e_i(P(a_1),P(a_2),...,P(a_m)) \equiv e_i(P(\omega_1),P(\omega_2),...,P(\omega_m)) \pmod p$$implying the result.
Claim 2 : $Q^*(X)$ divides $X^{n!}-1$ (in $\mathbb{F}_p[X]$).

Proof : Since $\mathrm{ord}_p(a_1) = n$, we have $\mathrm{ord}_p(P(a_1))\leqslant n$ or $P(a_1)^{n!}\equiv 1\pmod p$. Hence each root of $Q^*(X)$ is root of $X^{n!}-1$, done.
Now we are ready to shift the local conditions into global conditions. Since $Q(X)$ must congruent to $Q*(X)$ in $\mathbb{F}_p[X]$, polynomial $Q(X)$ must congruent to some divisor of $X^{n!}-1$ in $\mathbb{F}_p[X]$.

By Pigeonhole's principle there exists infinitely many prime $q\equiv 1\pmod n$ which $Q(X)$ is congruent to same divisor $R(X)$ of $X^{n!}-1$ in $\mathbb{F}_q[X]$. This force all coefficients of $Q(X)-R(X)$ to be divisible by infinitely many prime $q$. Hence $Q(X) = R(X)\mid X^{n!}-1$, implying $P(\omega_i)^{n!} = 1$ as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pieater314159
202 posts
#9 • 2 Y
Y by Adventure10, Mango247
Here's another elementary solution:

Fix $n$, and let $p$ vary across all primes equivalent to $1\bmod n$. Now, for all $x$ for which $x^n\equiv 1\bmod p$, we have

$$P(x)^{n!}\in\{0,1\}\bmod p\implies P(x)^{n!+1}-P(x).$$
(we get $1$ if we can apply our condition and otherwise we get $0$). Let $Q(x)=P(x)^{n!+1}-P(x)$, and write

$$Q(x)=R(x)+S(x)(x^n-1)$$
where $\deg(R)<n$ (we do this in $\mathbb{Z}[x]$). Now, for all $p\equiv 1\bmod n$, we have that $Q(x)\equiv 0\bmod p$ if $x^n=\equiv 1\bmod p$, which means that $R(x)\equiv 0\bmod p$. As $R$ has $n$ roots in $\mathbb{F}_p$ and it is of degree $\leq n-1$, we have that $R$ must be equivalent to the zero polynomial $\bmod p$, and thus all of the coefficients of $R$ are divisible by $p$. Now, as this holds for infinitely many $p$, we see that $R(x)$ is identically $0$, or that

$$x^n-1\big|P(x)^{n!+1}-P(x).$$
This implies that, if $x=\zeta_n$ is a primitive $n$th root of unity,

$$P(\zeta_n)=0\mathrm{\ or\ }P(\zeta_n)^{n!}=1\implies |P(\zeta_n)|=1.$$
One of these two criteria must hold for infinitely many $n$. If it is the first, then $P$ has infinitely many roots and is identically $0$. If it is the second, then, letting $d$ be the degree of $P$,

$$P(z)z^dP\left(\frac{1}{z}\right)=z^d$$
holds for infinitely many $z$; as this is a polynomial equation these must be identical as polynomials. We claim the only solutions to this are of the form $\pm x^d$. Assume we have a counterexample $P$ with minimal degree. As $P(x)/x$ would be a counterexample if $P(0)$ were equal to $0$, we conclude that $P(0)\neq 0$. However, as $z\to\infty$ ($z$ real), the left side is of order $P(0)z^d(cz^d)$ ($c$ is the leading coefficient) while the right side is $z^d$, allowing us to conclude (as $cP(0)\neq 0$), that $d=0$ and $P$ is constant, which implies that if $P\equiv c$ we have $c^2=1$, which is exactly our solution set. Now, if $P(x)=x^d$ we have a valid solution and if $P(x)=-x^d$ we have a contradiction at $n=1$ and $p=3$, so the only solutions are $P(x)=0$ and $P(x)=x^d$, finishing the proof.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#10 • 1 Y
Y by ihategeo_1969
Solution from Twitch Solves ISL:

The answer is $P(n) = n^{d}$ only for $d \ge 0$, which clearly works.
For the other direction, we assume $P$ is nonconstant, and let $\ell$ be a large prime, say $\ell > 100 (\deg P + 100)^2$.

Claim: For this prime $\ell$, we have a divisibility of ${\mathbb Z}[X]$-polynomials \[ \Phi(X) \coloneqq X^{\ell-1} + X^{\ell-2} + \dots + 1 \mid P(X)^\ell - 1. \]Proof. Because $\Phi$ is irreducible and has large degree, it is coprime to both $P(n)$ and $P(n) \pm1$. Then there exists a constant $C$ such that \[ \gcd(\Phi(n), P(n)(P(n)^2-1)) \le C \]for all $n$, by Bezout.
Consider large primes $p > C$ such that
  • $p \not\equiv 1 \pmod q$ for any prime $3 \le q < \ell$,
  • $p \equiv 1 \pmod \ell$.
There are infinitely many such primes by Dirichlet. For each such $p$, we can find $n$ such that $p \mid \Phi(n)$, simply by taking $g$ to be a primitive modulo $p$, and choosing $n = g^{\frac{p-1}{\ell}}$.
For that $n$ we have $p \mid n^\ell-1$, so the order of $n$ is at most $\ell$. Consequently, $p$ divides \[ P(n) \cdot (P(n)-1) \cdot (P(n)^2-1) \cdot \dots \cdot (P(n)^{\ell}-1). \]Now $p$ has to divide these factors. It doesn't divide $P(n)$ as $p > C$. And if it divided $P(n)^k-1$ for some $k < \ell$, then the order of $P(n)$ modulo $p$ would be a divisor of $k$. But it should also divide $\ell-1$, and because of constraints on $p$ this would be force the order to be at most $2$. From $p > C$, that's impossible too. Hence $p$ divides $P(n)^\ell-1$, the last factor.
In other words, we have shown there are arbitrarily large primes such that $p$ divides $\Phi(n)$ and $P(n)^\ell-1$ for some $\ell$. Hence (via the same Bezout argument) it follows $\Phi(X)$ is not coprime to $P(X)^\ell-1$ and hence divides it. $\blacksquare$
Now let $\zeta$ be a primitive $\ell$th root of unity. Then $P(\zeta)$ is an $\ell$th root of unity as well, so \[ P(\zeta) - \zeta^d = 0. \]for some integer $r$, say $0 \le d \le \ell-1$. However, $\Phi(X) \coloneqq X^{\ell-1} + X^{\ell-2} + \dots + 1$ is the minimal polynomial of $\zeta$, and $\deg P \ll \ell$. Reading the coefficients of our nonconstant $P$, this could only happen if $P(X) = X^d$ exactly, as desired.

Remark: The last step of the argument really uses the fact we have $P(X)^\ell-1$. It would not work if we instead had $P(X)^k-1$ for some $k < \ell$, because then the $\operatorname{lcm}(k,\ell)$th cyclotomic polynomial may not be so well-behaved. That's why in the proof of the claim we had to some modular condition on $p$ (with $p \not\equiv 1 \pmod q$ for all $q$) to rule out the possibility that $p$ divided any of the other factors. If one tries the argument at first with just generic large $p$ dividing an element in the range of $\Phi$, one would instead get $\Phi(X) \mid P(X)^k-1$ for some $k$ depending on $\ell$, leading to the issue above.
Z K Y
N Quick Reply
G
H
=
a