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
IMO 2009, Problem 3
orl   52
N 17 minutes ago by N3bula
Source: IMO 2009, Problem 3
Suppose that $ s_1,s_2,s_3, \ldots$ is a strictly increasing sequence of positive integers such that the sub-sequences \[s_{s_1},\, s_{s_2},\, s_{s_3},\, \ldots\qquad\text{and}\qquad s_{s_1+1},\, s_{s_2+1},\, s_{s_3+1},\, \ldots\] are both arithmetic progressions. Prove that the sequence $ s_1, s_2, s_3, \ldots$ is itself an arithmetic progression.

Proposed by Gabriel Carroll, USA
52 replies
orl
Jul 15, 2009
N3bula
17 minutes ago
Find all functions $f$: \(\mathbb{R}\) \(\rightarrow\) \(\mathbb{R}\) such : $f(
guramuta   2
N 21 minutes ago by GreekIdiot
Find all functions $f$: \(\mathbb{R}\) \(\rightarrow\) \(\mathbb{R}\) such :
$f(x+yf(x)) + f(xf(y)-y) = f(x) - f(y) + 2xy$
2 replies
+1 w
guramuta
Yesterday at 2:18 PM
GreekIdiot
21 minutes ago
Two perpendiculars
jayme   1
N 36 minutes ago by ND_
Source: Own?
Dear Mathlinkers,

1. ABC a triangle
2. 0 the circumcircle
3. D the pole of BC wrt 0
4. B', C' the symmetrics of B, C wrt AC, AB
5. 1b, 1c the circumcircles of the triangles BB'D, CC'D
6. J the center of 1b
7. V the second point of intersection of DJ and 1c.

Prove : CV is perpendicular to BC.

Sincerely
Jean-Louis
1 reply
jayme
4 hours ago
ND_
36 minutes ago
Another triangle
Rushil   14
N 43 minutes ago by SomeonecoolLovesMaths
Source: Indian RMO 1991 Problem 1
Let $P$ be an interior point of a triangle $ABC$ and $AP,BP,CP$ meet the sides $BC,CA,AB$ in $D,E,F$ respectively. Show that \[ \frac{AP}{PD} = \frac{AF}{FB} + \frac{AE}{EC}.  \]
Remark
14 replies
Rushil
Oct 15, 2005
SomeonecoolLovesMaths
43 minutes ago
Pertenacious Polynomial Problem
BadAtCompetitionMath21420   6
N Today at 3:51 AM by lbh_qys
Let the polynomial $P(x) = x^3-x^2+px-q$ have real roots and real coefficients with $q>0$. What is the maximum value of $p+q$?

This is a problem I made for my math competition, and I wanted to see if someone would double-check my work (No Mike allowed):

solution
Is this solution good?
6 replies
BadAtCompetitionMath21420
May 17, 2025
lbh_qys
Today at 3:51 AM
Vieta's Formula.
BlackOctopus23   4
N Today at 3:11 AM by compoly2010
Can someone help me understand Vieta's Formula? I am currently learning it for my class. I learned that for a polynomial of degree $n$, all the roots added will give $-\frac{a_{n-1}}{a_n}$. I also learned that if every single root, multiplies every single root, it will give $\frac{a_{n-2}}{a_n}$. I also learned that if all the roots are multiplied, it will give $-\frac{a_0}{a_n}$. Is this right? And is there any purpose for these equations?
4 replies
BlackOctopus23
Yesterday at 11:10 PM
compoly2010
Today at 3:11 AM
The sum of 335 distinct positive integers
Streit31415   1
N Today at 12:36 AM by Bocabulary142857
The sum of 335 distinct positive integers is equal to 100000
a) what is the minimum number of odd numbers among them ?
b) what is the maximum number of odd numbers among them ?
1 reply
Streit31415
Yesterday at 11:38 PM
Bocabulary142857
Today at 12:36 AM
Diophantine Equation (cousin of Mordell)
urfinalopp   4
N Yesterday at 10:54 PM by FoeverResentful
Find pairs of integers $(x;y)$ such that:

$x^2=y^5+32$
4 replies
urfinalopp
Yesterday at 6:38 PM
FoeverResentful
Yesterday at 10:54 PM
p+2^p-3=n^2
tom-nowy   1
N Yesterday at 6:51 PM by urfinalopp
Let $n$ be a natural number and $p$ be a prime number. How many different pairs $(n, p)$ satisfy the equation:
$$p + 2^p - 3 = n^2 .$$
Inspired by https://artofproblemsolving.com/community/c4h3560823
1 reply
tom-nowy
Yesterday at 11:16 AM
urfinalopp
Yesterday at 6:51 PM
Perfect cubes
Entrepreneur   6
N Yesterday at 6:23 PM by NamelyOrange
Find all ordered pairs of positive integers $(a,b,c)$ such that $\overline{abc}$ and $\overline{cab}$ are both perfect cubes.
6 replies
Entrepreneur
Yesterday at 6:04 PM
NamelyOrange
Yesterday at 6:23 PM
Ez comb proposed by ME
IEatProblemsForBreakfast   1
N Yesterday at 3:09 PM by n1g3r14n
A and B play a game on two table:
1.At first one table got $n$ different coloured marbles on it and another one is empty
2.At each move player choose set of marbles that hadn't choose either players before and all chosen marbles from same table, and move all the marbles in that set to another table
3.Player who can not move lose
If A starts and they move alternatily who got the winning strategy?
1 reply
IEatProblemsForBreakfast
Yesterday at 9:02 AM
n1g3r14n
Yesterday at 3:09 PM
geometry
luckvoltia.112   0
Yesterday at 3:04 PM
ChGiven an acute triangle ABC inscribed in circle $(O)$ The altitudes $BE, CF$ , intersect
each other at $H$. The tangents at $B$ and $C $of $(O)$ intersect at $S$. Let $M $be the midpoint of $BC$. $EM$ intersects $SC$
at $I$, $FM$ intersects $SB$ at $J.$
a) Prove that the points $I, S, M, J$ lie on the same circle.
b) The circle with diameter $AH$ intersects the circle $(O)$ at the second point $T.$ The line $AH$ intersects
$(O)$ at the second point $K$. Prove that $S,K,T$ are collinear.
0 replies
luckvoltia.112
Yesterday at 3:04 PM
0 replies
Exponents of integer question
Dheckob   4
N Yesterday at 2:45 PM by LeYohan
Find the smallest positive integer $m$ such that $5m$ is an exact 5th power, $6m$ is an exact 6th power, and $7m$ is an exact 7th power.
4 replies
Dheckob
Apr 12, 2017
LeYohan
Yesterday at 2:45 PM
Inequalities
sqing   3
N Yesterday at 1:49 PM by sqing
Let $ a,b>0   $ . Prove that
$$ \frac{a}{a^2+a +2b+1}+ \frac{b}{b^2+2a +b+1}  \leq  \frac{2}{5} $$$$ \frac{a}{a^2+2a +b+1}+ \frac{b}{b^2+a +2b+1}  \leq  \frac{2}{5} $$
3 replies
sqing
May 13, 2025
sqing
Yesterday at 1:49 PM
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