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
interesting functional
Pomegranat   2
N 23 minutes ago by Pomegranat
Source: I don't know sorry
Find all functions \( f : \mathbb{R}^+ \to \mathbb{R}^+ \) such that for all positive real numbers \( x \) and \( y \), the following equation holds:
\[
\frac{x + f(y)}{x f(y)} = f\left( \frac{1}{y} + f\left( \frac{1}{x} \right) \right)
\]
2 replies
Pomegranat
2 hours ago
Pomegranat
23 minutes ago
Function equation algebra
TUAN2k8   1
N 25 minutes ago by TUAN2k8
Source: Balkan MO 2025
Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that for all $x \in \mathbb{R}$ and $y \in \mathbb{R}$,
\begin{align}
f(x+yf(x))+y=xy+f(x+y).
\end{align}
1 reply
TUAN2k8
40 minutes ago
TUAN2k8
25 minutes ago
Functional equation with a twist (it's number theory)
Davdav1232   1
N 25 minutes ago by NO_SQUARES
Source: Israel TST 8 2025 p2
Prove that for all primes \( p \) such that \( p \equiv 3 \pmod{4} \) or \( p \equiv 5 \pmod{8} \), there exist integers
\[
1 \leq a_1 < a_2 < \cdots < a_{(p-1)/2} < p
\]such that
\[
\prod_{\substack{1 \leq i < j \leq (p-1)/2}} (a_i + a_j)^2 \equiv 1 \pmod{p}.
\]
1 reply
Davdav1232
Thursday at 8:32 PM
NO_SQUARES
25 minutes ago
Coolabra
Titibuuu   3
N an hour ago by sqing
Let \( a, b, c \) be distinct real numbers such that
\[
a + b + c + \frac{1}{abc} = \frac{19}{2}
\]Find the maximum possible value of \( a \).
3 replies
Titibuuu
Today at 2:21 AM
sqing
an hour ago
HMMT Masters Round
rrusczyk   0
Feb 16, 2011
For those of you college students who miss the camaraderie and challenge of on-site math competitions, the Harvard-MIT Math Tournament offers a college competition. Here's a note from Maria Monks and Rishi Gupta, AoPSers who are running the competition:

[quote="Maria Monks and Rishi Gupta"]
The HMMT (Harvard-MIT Math Tournament) Masters Round is an annual math contest for undergraduates, written by former HMMT directors and problem czars. The contest aims to bring the spirit of competition and the art of problem solving into higher mathematics, with challenging problems in abstract algebra, analysis, topology, combinatorics, calculus, linear algebra, and number theory at the undergraduate level. The Masters Round will consist of a 4 hour, proof-based test with 10 questions of varying difficulty.

Any student currently enrolled in an undergraduate institution is eligible to compete, and awards are given to the top 7 undergraduates. Additionally, there will be prizes awarded for particularly clever or elegant solutions. College graduates may also compete, but they will not be eligible for awards.

The team scoring is as follows. Any undergraduate institution with more than five participating undergraduates automatically becomes a team, and that team comprises all the undergraduates from that school. A school's team score is the sum of the ranks of the top 5 individuals from that school, after all non-team participants are removed from the results. Ties are broken by the 6th place individuals from the respective schools.

Problem submissions from college graduates are welcome. Please send any ideas you may have to hmmt-masters@mit.edu. College graduates are also invited to help grade after the contest on April 2, including those who are competing unofficially, and free dinner will be provided for volunteers.

The second annual Masters Round will be held at Harvard University in the Science Center, Hall A, on April 2, 2011. For details and to sign up, please visit http://hmmt.mit.edu/masters. Hope to see you there![/quote]
0 replies
rrusczyk
Feb 16, 2011
0 replies
AMC changes
DPatrick   3
N Dec 2, 2010 by dragon96
Today the American Mathematics Competitions announced changes to the AMC10/12 - AIME - USA(J)MO series of contests for high school students.

There are two major changes:

1. The cutoff score to advance from the AMC10 to the AIME is still 120, but in the event that fewer than 2.5% of all students score 120 or higher, they will lower the cutoff score so that the top 2.5% of students advance. (In previous years this percentage was 1%.) (Also, no changes for advancement from AMC12 to AIME: it's still 100 or the top 5%.)

2. Students can qualify for the USAMO only by taking the AMC12. Students can qualify for the USAJMO only by taking the AMC10. If a student takes both the AMC10 and AMC12 and qualifies for both olympiads, he or she must take the USAMO.

Official rules are on the AMC's website. Discussion continues on our AMC forum.
3 replies
DPatrick
Dec 1, 2010
dragon96
Dec 2, 2010
Math Prize for Girls
DPatrick   1
N Nov 15, 2010 by fprosk
Congratulations to all the winners and participants in the 2010 Math Prize for Girls, which was held this past weekend in New York.

Ravi Boppana, the director of the contest, has very graciously posted all of the problems on our forum.
1 reply
DPatrick
Nov 15, 2010
fprosk
Nov 15, 2010
USAMTS 2010-11 has started!
DPatrick   0
Oct 8, 2010
The 2010-11 edition of the USA Mathematical Talent Search is now underway. The Round 1 problems have been posted on http://www.usamts.org, and the deadline to submit solutions is November 22.

The USAMTS is different from most math contests: you get several weeks to think about the problems. You can use any resources you like to help you explore the problems (other than asking other people). Then you write up full solutions showing all your work. You'll not only receive scores for your work, but you'll also receive individual feedback on your solutions.

For those who have participated in the past, you'll notice a new format for 2010-11: we're doing 2 rounds of 6 problems each this year. There are many, many more activities in the math contest universe now as compared to when the USAMTS was founded in the late 1980s, and as such we felt that a more streamlined USAMTS would give students more opportunity to participate in both the USAMTS and in other mathematical activities.
0 replies
DPatrick
Oct 8, 2010
0 replies
International Math Olympiad Problems Now Available
rrusczyk   1
N Jul 9, 2010 by phiReKaLk6781
The problems from the 2010 International Math Olympiad are now available here (in many languages). You can join discussion of the problems on AoPS here. Best of luck to all our community members at the IMO!
1 reply
rrusczyk
Jul 8, 2010
phiReKaLk6781
Jul 9, 2010
No more topics!
Sum-free multiplicative group mod p can be arbitrarily large
v_Enhance   25
N Apr 18, 2025 by Ilikeminecraft
Source: USA January TST for the 55th IMO 2014
For a prime $p$, a subset $S$ of residues modulo $p$ is called a sum-free multiplicative subgroup of $\mathbb F_p$ if
$\bullet$ there is a nonzero residue $\alpha$ modulo $p$ such that $S = \left\{ 1, \alpha^1, \alpha^2, \dots \right\}$ (all considered mod $p$), and
$\bullet$ there are no $a,b,c \in S$ (not necessarily distinct) such that $a+b \equiv c \pmod p$.
Prove that for every integer $N$, there is a prime $p$ and a sum-free multiplicative subgroup $S$ of $\mathbb F_p$ such that $\left\lvert S \right\rvert \ge N$.

Proposed by Noga Alon and Jean Bourgain
25 replies
v_Enhance
Apr 28, 2014
Ilikeminecraft
Apr 18, 2025
Sum-free multiplicative group mod p can be arbitrarily large
G H J
Source: USA January TST for the 55th IMO 2014
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#1 • 10 Y
Y by langkhach11112, Davi-8191, HamstPan38825, HWenslawski, megarnie, Adventure10, Mango247, ehuseyinyigit, ys-lg, and 1 other user
For a prime $p$, a subset $S$ of residues modulo $p$ is called a sum-free multiplicative subgroup of $\mathbb F_p$ if
$\bullet$ there is a nonzero residue $\alpha$ modulo $p$ such that $S = \left\{ 1, \alpha^1, \alpha^2, \dots \right\}$ (all considered mod $p$), and
$\bullet$ there are no $a,b,c \in S$ (not necessarily distinct) such that $a+b \equiv c \pmod p$.
Prove that for every integer $N$, there is a prime $p$ and a sum-free multiplicative subgroup $S$ of $\mathbb F_p$ such that $\left\lvert S \right\rvert \ge N$.

Proposed by Noga Alon and Jean Bourgain
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mavropnevma
15142 posts
#2 • 5 Y
Y by bcp123, langkhach11112, Adventure10, Mango247, ehuseyinyigit
I wonder if this problem was "inspired" from the result(s) of this article http://www.cs.tau.ac.il/~nogaa/PDFS/multip1.pdf of Noga Alon :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dinoboy
2903 posts
#3 • 12 Y
Y by SCP, narutomath96, TheStrangeCharm, langkhach11112, rafayaashary1, Leooooo, fields123, chem123, solver1948, xhx0123, Adventure10, Mango247
The key insight to this problem is to transfer it over the the complex numbers, where roots of unity behave a lot more nicely. Fix $q > \max(N,3)$ and let $S$ be the set of $q^{th}$ roots of unity for a prime $p$. Now if $S$ were not sum free modulo $p$, there must exist $a,b$ such that:
\[
1 + \alpha^a \equiv \alpha^b \pmod{p}
\]
Exponentiation by $q$:
\[
(1 + \alpha^a)^q \equiv 1 \pmod{p}
\]
Now, I claim that $(1 + x^a)^q - 1$ and $x^q - 1$ are relatively prime polynomials over $\mathbb{Z}[x]$. This is clear as we have $1 + \omega^a$ is a $q^{th}$ root where $\omega$ is a $q^{th}$ root of unity, but this is impossible for $q > 3$. Thus there exist $m(x), n(x) \in \mathbb{Z}[x]$ and an integer $c_a$ such that:
\[
m(x) ((1 + x^a)^q - 1) + n(x) (x^q - 1) = c_a
\]
Now if $p > c_a$, we get $p$ cannot simultaneously divide $(1 + x^a)^q - 1$ and $x^q - 1$. Thus if we set $p \equiv 1 \pmod{q}$ with $p > c_0, c_1, ..., c_{q-1}$, we get $S$ must be sum free as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathocean97
606 posts
#4 • 7 Y
Y by langkhach11112, Supercali, Nathanisme, TheBarioBario, Adventure10, Mango247, RootofUnityfilter
During the actual test I found a pretty funny proof. Throughout when say polynomial, I mean integer polynomial (I may have forgotten to mention it at places)

For some preliminary stuff, we need $\alpha^x+\alpha^y \not= \alpha^z$ for any integers $0 \le x, y, z \le p-2$. Dividing through by $\alpha^z$ gives $\alpha^{x-z}+\alpha^{y-z} \not= 1$, and letting $c = x-z, d = y-z$ we just need that $\alpha^c+\alpha^d \not= 1$.
This motivates us to look at polynomials of the form $x^c+x^d-1$. (*)

Lemma 1: For some polynomial $f(x) \in \mathbb{Z}[x]$ such that $f(1)$ is odd, we can find a polynomial $g(x^2)$ such that $f(x) | g(x^2)$ and $g(1)$ is also odd.

Proof: Let $g(x^2) = f(x)f(-x)$, because both sides are even functions. But then $g(1) = f(1)f(-1) \equiv f(1)^2 \equiv 1 \pmod{2}$.

Note that this implies that for any positive integer $N$ we can find a polynomial $h$ such that $f(x) | h\left(x^{2^N}\right)$ and such that $h(1)$ is odd, by induction.

Now choose primes of the form $p = k \cdot 2^N+1$ (infinitely many by Dirichlet's theorem) only and fix $\alpha$ to have order $2^N$. By (*) we now consider the polynomials of the form $x^c+x^d-1$ for $0 \le c, d \le 2^N$ and we prove that for all large enough $p$ $\alpha$ will not be a root in $\mathbb{F}_p$. Assume $\alpha$ is a root. Let $f(x) = x^c+x^d-1$, and by Lemma 1 (the note afterwards) that we can find a $h$ such that $f(x) | h\left(x^{2^N}\right)$. If $\alpha$ is a root of $f$, plugging in $\alpha$, we get that we need that $h\left(\alpha^{2^N}\right) \equiv h(1) \pmod{p}$ to equal 0. But $h(1)$ is fixed for any primes $p$ and it is odd by the Lemma (since $f(1) = 1$ is odd), so it is not identically 0. So $\alpha$ is eventually not a root. Since we can do this for any polynomials $f(x)$ for $0 \le c, d \le 2^N$, eventually $\alpha$ will not be a root of any of them, so we're done.

Note: You can also replace $2$ (even) by any prime $q$ and essentially repeat the above argument.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math154
4302 posts
#5 • 3 Y
Y by langkhach11112, Adventure10, Mango247
mavropnevma wrote:
I wonder if this problem was "inspired" from the result(s) of this article http://www.cs.tau.ac.il/~nogaa/PDFS/multip1.pdf of Noga Alon :)
"Inspired" is quite a generous word. :P As briefly hinted at in the end of that paper, it is not hard to extend the methods to show that the "$0\notin S+S-S$" condition of (b) can be replaced by $0\notin a_1S+a_2S+\cdots+a_kS$ (for integers $a_i$) if and only if $\sum a_i \ne 0$.

Then the gimmicky stuff like "$1+\omega,\omega$ can't simultaneously be $q$th roots for large $q$" doesn't work, although as mathocean97 notes, the argument isn't too much harder.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dinoboy
2903 posts
#6 • 3 Y
Y by langkhach11112, Adventure10, Mango247
math154 wrote:
Then the gimmicky stuff like "$1+\omega,\omega$ can't simultaneously be $q$th roots for large $q$" doesn't work.

I wouldn't call it gimmicky as it generalizes as well. Basically instead we would have to show if $P$ is a polynomial with integer coefficients whose coefficients do not sum to 1, then there exists some sufficiently large $n$ such that $P(\omega_n)$ is not an $n^{th}$ root of unity and then we take an $n$ larger than the required $n$'s for each of the possible polynomials. But this is simple using the fact $[\mathbb{Q}[\omega_n]:\mathbb{Q}] = \varphi(n)$, as then we can just take $n$ with $\varphi(n) >  \deg P +1$. Note that the coefficient summing to one condition comes into play as we may get $P(x) = x^k$ in that case which breaks the argument but otherwise we are fine.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math154
4302 posts
#7 • 1 Y
Y by Adventure10
dinoboy wrote:
math154 wrote:
Then the gimmicky stuff like "$1+\omega,\omega$ can't simultaneously be $q$th roots for large $q$" doesn't work.

I wouldn't call it gimmicky as it generalizes as well.
I was just saying the usual geometry proof of this doesn't work well (which most people who solved the problem live did, although I know you know better). I basically had the same approach as you (which is actually also the same as mathocean97's, if you look closely enough at the $g$/$h$ he constructs).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JuanOrtiz
366 posts
#8 • 3 Y
Y by langkhach11112, Adventure10, Mango247
The key idea is that there are $m$ $m$-th roots of unity, so if we take $p$ big, these roots of unity should be "spaced out". Another very important idea is to consider polynomials in $\mathbb{Z}$, and then evaluate them mod $p$.

Let's look at polynomials. If the problem was wrong, then for $p$ sufficiently big, the $Q$-th roots of unity mod $p$ don't work. So there exists a solution to $(1+x^b)^Q-1=x^Q-1=0$ mod $p$. Let $A(x)=(1+x^b)^Q-1$ and let $B(x)=x^Q-1$. Since $w+1$ and $w$ cannot both be roots of unity (in $\mathbb{C}$) when $Q$ is big, we have that $A$ ad $B$ are coprime polynomials. And so we have $mA+nB=c$ for some $m,n$ polynomials, $c$ a nonzero nteger. We have that for all $p \equiv 1$ (mod $Q$) there must exist a $b$ such that $p | c$. But we can simply take a very gigantic $p$, greater than all $Q$ possible values of $c$ (since there are $Q$ possible values of $b$). This $p$ exists by Dirichlet. So we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Tuananh98
3 posts
#9 • 1 Y
Y by Adventure10
https://www.facebook.com/photo.php?fbid=341156276033763&set=a.300473743435350.1073741828.100004181803371&type=1&theater
I wrote my solution here in Vietnamese but i think it's very easy to understand:))))
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bcp123
676 posts
#10 • 2 Y
Y by Adventure10, Mango247
dinoboy wrote:
and let $S$ be the set of $q^{th}$ roots of unity for a prime $p$.
Can someone explain this?
This post has been edited 1 time. Last edited by bcp123, Nov 11, 2015, 2:59 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathocean97
606 posts
#11 • 4 Y
Y by bcp123, langkhach11112, Adventure10, Mango247
It's actually exactly what you would expect. It's the solutions to $x^q \equiv 1 \pmod{p}$. If $q | p-1$, then there are exactly $q$ roots of unity $\pmod{p}$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pi37
2079 posts
#12 • 3 Y
Y by langkhach11112, Adventure10, Mango247
Basic idea: we want to translate the sum-free condition with small $S$ to be a kind of finite restriction, which taking $p$ sufficiently large can break.

So fix some $k$ to be the size of $S$ and let $p$ be some indeterminate prime for now with $p\equiv 1 \pmod k$. Of course, if the sum-free condition fails then there are two elements of the group which add to one. Thus there would exist $g$ such that both $g^k\equiv 1\pmod{p}$ and $(1-g)^k\equiv 1 \pmod{p}$. Now we decide to take $p\equiv 2\pmod{3}$, so the polynomials $x^k-1$ and $(1-x)^k-1$ have no shared complex roots and are thus relatively prime. Then there exist $p,q\in \mathbb{Z}[x]$ such that
\[
p(x)(x^k-1)+q(x)((1-x)^k-1)=n
\]for some positive integer $n$. Thus since there exists $g$ which makes the LHS vanish $\pmod{p}$, if $p\nmid n$, then the subgroup is sum-free. Thus all we have to do is take $p>n$, with $p\equiv 1 \pmod{k}$ and $p\equiv 2\pmod{3}$ by Dirichlet, and we're done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DrMath
2130 posts
#13 • 2 Y
Y by primesarespecial, Adventure10
Let $q$ be a prime, and let $z$ be a primitive $q$th root of unity. Then let $f(X)=\prod_{i, j} (X-z^i-z^j) \in \mathbb{Z}[X]$. First, note that $f(z^k)=\prod_{i,j} (z^k-z^i-z^j)=\prod_{i, j} (z^{k'}-z^{i+k'-k}-z^{j+k'-k})=\prod_{i', j'} (z^{k'}-z^{i'}-z^{j'})=f(z^{k'})$. This means that $f(X)=g(X)(X^q-1)+r$ for some finite constant $r$. Moreover, this constant is nonzero, as if $f(1)=0$ then $1=z^i+z^j$ for some $i,j$. But then this means that the minimal polynomial of $z$ would be $X^i+X^j-1$ which has degree greater than 0 but at most $q-1$, contradiction. Thus $r\neq 0$. But then note that if we take $q-1\mid p$ and $p>r$, then $X^q-1\nmid f(X)$ in $\mathbb{F}_p[X]$. Then if $\alpha\in\mathbb{F}_p$ such that $\alpha^q=1$, then $f(X)=\prod_{i,j} (X-\alpha^i-\alpha^j)$ which decomposes into linear factors in $\mathbb{F}_p[X]$. But also note $f(\alpha)\neq 0$, so in particular it cannot be true that $\alpha=\alpha^i+\alpha^j$ for any $i,j$ and we are done.

Now $|S|=q$, and we can make $q$ arbitrarily large, so we are done.
This post has been edited 1 time. Last edited by DrMath, Apr 9, 2017, 6:47 PM
Reason: forgot last line
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
anantmudgal09
1980 posts
#14 • 2 Y
Y by Adventure10, Mango247
This feels a little bit easy for TST #6, so I'm probably missing something :maybe:
v_Enhance wrote:
For a prime $p$, a subset $S$ of residues modulo $p$ is called a sum-free multiplicative subgroup of $\mathbb F_p$ if
$\bullet$ there is a nonzero residue $\alpha$ modulo $p$ such that $S = \left\{ 1, \alpha^1, \alpha^2, \dots \right\}$ (all considered mod $p$), and
$\bullet$ there are no $a,b,c \in S$ (not necessarily distinct) such that $a+b \equiv c \pmod p$.
Prove that for every integer $N$, there is a prime $p$ and a sum-free multiplicative subgroup $S$ of $\mathbb F_p$ such that $\left\lvert S \right\rvert \ge N$.

Proposed by Noga Alon and Jean Bourgain

Let $d=2^{|N|+1}$ and $p \equiv 1 \pmod{d}$ be a prime. Then pick $\alpha$ with $d$ the minimal number such that $\alpha^d \equiv 1 \pmod{p}$. Then we claim that the set $S=\{1, \alpha, \alpha^2, \dots\}$ works fine. Clearly, $|S|>N$ and $S$ has the given type. Now we prove that $\alpha^m+\alpha^n=\alpha^k$ has no solution mod $p$. Equivalently, $1+\alpha^c=\alpha^b \pmod{p}$ does not happen for any $b,c$. Note that in $\mathbb{F}_p[x]$ we have $$X^d-1=\prod_{s \in S} (X-s)$$so we wish to show that $X-s$ is not a factor of $(X+1)^d-1$. We just need to show that their $\gcd$ is $1$. Suppose $f(x) \in \mathbb{Z}[x]$ is their gcd (non-constant else its actually $1$); then $f(x)$ divides them both in $\mathbb{F}_2[x]$ as well. However, they have gcd $1$ in $\mathbb{F}_2[x]$ since $(X+1)^{2{|N|+1}}-1 \equiv X^{2^{|N|+1|}}$ by Frobenius Endomorphism. Thus, $f(x)=1+2g(x)$ for some integer polynomial $g$. However $f$ must be monic as it integrally divides two monic integer polynomials; contradiction!

Edit: Okay, so a constant gcd may not be $1$. Suppose we can find $q(x), r(x) \in \mathbb{Z}[x]$ with $$q(x)(x^d-1)+r(x)((x+1)^d-1)=M$$for fixed integer $M$. Then take $p>M$ to avoid mod $p$ issues. Hope this fixes it?
This post has been edited 1 time. Last edited by anantmudgal09, Jun 17, 2018, 12:56 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
neel02
66 posts
#15 • 2 Y
Y by Adventure10, Mango247
Hi @anantmudgal09 ! Hope you not [missing anything] since usatst 2016 Dec.# 3 is an another ex. of unbelieveably easy prob ! :P
This post has been edited 1 time. Last edited by neel02, Jun 17, 2018, 9:07 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Kayak
1298 posts
#16 • 1 Y
Y by Adventure10
Can someone point out any mistake in my "solution" ? This looks way too simple for it's position.

???
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yayups
1614 posts
#17 • 1 Y
Y by Adventure10
Let $N$ be some positive integer relatively prime to $3$. Pick $p\equiv 1\pmod{N}$ to be a prime much much larger than $N$. We show that there exists a sum free multiplicative subgroup of $\mathbb{F}_p$ of size $N$. But first, we need a lemma.

Lemma: $\gcd(X^N-1,(1-X)^N-1)=1$ over $\mathbb{F}_p[X]$.

Proof of Lemma: Over $\mathbb{C}$, we can check that $X^N-1$ and $(1-X)^N-1$ share no roots. Indeed, if $r$ was a root of both, then $|r|=|1-r|=1$. This would mean that $(1-r)(1-1/r)=1$, or that $r+1/r=1$, or $r^2-r+1=0$. Thus, $r^6=1$, but since $\gcd(N,3)=1$, we have $r^N\ne 1$, a contradiction. Thus, $\gcd(X^N-1,(1-X)^N-1)=1$ over $\mathbb{Z}[X]$ as well, so there are fixed polynomials $P(X),Q(X)$ such that
\[(X^N-1)P(X)+((1-X)^N-1)Q(X)=1.\]Now, for $p$ sufficiently large, both $P(X)$ and $Q(X)$ won't be $0$, so then $\gcd(X^N-1,(1-X)^N-1)=1$ over $\mathbb{F}_p[X]$. $\blacksquare$

Now, suppose $g$ is a primitive root mod $p$. Let $\alpha=g^{\frac{p-1}{N}}$, so $S$ has size $N$. Now, suppose we had $\alpha^i+\alpha^j\equiv\alpha^k\pmod{p}$. Then, $\alpha^{i-k}+\alpha^{j-k}\equiv 1\pmod{p}$, so WLOG we can take $k=0$. Thus, $\alpha^j\equiv 1-\alpha^i\pmod{p}$, so letting $r=\alpha^i$, we have $r,1-r$ are both roots of $X^N-1$ over $\mathbb{F}_p$. But this can't be by the lemma, so we have the desired contradiction. So we have constructed a sum free multiplicative subgroup of $\mathbb{F}_p$ for some $p$, of arbitrarily large size, as desired. $\blacksquare$
This post has been edited 1 time. Last edited by yayups, Feb 19, 2019, 6:52 AM
Reason: typo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lminsl
544 posts
#18 • 3 Y
Y by magicarrow, Nathanisme, Adventure10
Fix some prime $q$ bigger than $N$.

We will set $p$ as a prime dividing $\Phi_{q}(\alpha)$, and $S$ generated by powers of $\alpha$ modulo $p$, where $\alpha$ is a integer determined later. Note that $|S|=q$ here, so $S$ satisfies the size condition.

The main observation is the following:

Main Lemma: For coprime polynomials $f, g\in \mathbb{Z}[x]$, there exist a integer $C>0$ such that $\gcd(f(n), g(n))$ divides $C$ for every integer $n$ satisfying $\left( f(n), g(n) \right) \neq (0, 0)$.

Since $\Phi_q(x)$ is irreducible over $\mathbb{Z}[x]$, for every $0\le i<j <q$, the polynomials $\Phi_q(x)$ and $x^i+x^j-1$ is coprime, so some suitable $C_{i, j}$ exists by the lemma. Now set $\alpha$ such that $\alpha$ is divisible by all such $C_{i, j}$'s, then $\Phi_q(\alpha) \equiv 1 \pmod {C_{i, j}}$, so $\Phi_q(\alpha)$ and $\alpha^i+\alpha^j-1$ are coprime as integers.

Now, we prove that the set $S$ is sum-free. Assume that there exists some $i<j<k$ such that $\alpha^i +\alpha^j \equiv \alpha^k \pmod p$. Multiplying $\alpha^{q-k}$ in each sides give $\alpha^{i+q-k}+\alpha^{j+q-k}-1 \equiv 0 \pmod p$, whereas $p | \Phi_q(\alpha)$ is coprime with $\alpha^{i+q-k}+\alpha^{j+q-k}-1$. Hence $S$ is sum-free, and we're done!
This post has been edited 2 times. Last edited by lminsl, Feb 5, 2020, 3:26 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheUltimate123
1740 posts
#19 • 1 Y
Y by sabkx
I claim for every $n$ not divisible by $3$, we can choose a prime $p\equiv1\mod n$ such that there is a sum-free multiplicative subgroup in $\mathbb F_p$ of size $n$.

Let $P(x)=x^n-1$ and $Q(x)=(1+x^k)^n-1$. First I claim $P$ and $Q$ are relatively prime over $\mathbb C[x]$. If $P$ and $Q$ share a root $\omega$, then $\omega$ and $1+\omega^k$ are both roots of unity. Then the vectors defined by $\omega^k$, $1$, $-(1+\omega^k)$ form an equilateral triangle, which is absurd since $3\nmid n$.

Thus the greatest common factor of $P$ and $Q$ over $\mathbb Z[x]$ is a positive integer $m$, so by B\'ezout's lemma we may choose polynomials $A$ and $B$ in $\mathbb Z[x]$ with
\[
    A(x)\left(x^n-1\right)+B(x)\left[\left(1+x^k\right)^n-1\right]=m.\tag{$\star$}
\]Assume $S$ has size $n$ and choose a prime $p>m$ such that $p\equiv1\mod n$. A multiplicative subgroup exists by taking $\alpha=g^{(p-1)/n}$, where $g$ is a primitive root modulo $p$. If $S$ is not sum-free, then it contains elements $\alpha^x$, $\alpha^y$, $\alpha^z$ with $\alpha^x+\alpha^y=\alpha^z$. It follows that $(1+\alpha^{y-x})^n=1$, which is absurd since the left-hand expression vanishes modulo $p$ when taking $x=\alpha$ and $k=y-x$ in $(\star)$.
This post has been edited 1 time. Last edited by TheUltimate123, Feb 26, 2020, 6:46 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rcorreaa
238 posts
#20
Y by
Pick a prime $q>N$ and let $p$ be a prime number such that $q|p-1$. Choose $\alpha$ to be a primitive $q$-th root of unity $\pmod{p}$. Then, $S=\{1,\alpha,...,\alpha^{q-1}\} \implies$ for all $s \in S$, $s$ is a root of $X^q-1$ in $\mathbb{F}_p$.

From the second condition, the polynomial $\prod_{1 \leq i \leq j \leq q} (X-(\alpha^i+\alpha^j))$ is coprime to $X^q-1=\prod_{i=1}^q(x-\alpha^i)$ in $\mathbb{F}_p$, i.e., they don't share roots. Thus, we want $(\alpha^i+\alpha^j)^q \not \equiv 1 \pmod{p} \iff (1+\alpha^{j-i})^q \not \equiv 1 \pmod{p}$ for all $1 \leq i \leq j \leq q$. This is the same as saying that $(1+X)^q-1$ and $X^q-1$ don't share a common root modulo $p$.

Looking in $\mathbb{Z}[X]$, $(1+X)^q-1,X^q-1$ share a root if and only if $|z|=1=|z+1| \iff z=-\frac{1}{2} \pm \frac{\sqrt{3}}{2}i \implies$ as long as $3 \nmid q$, $gcd(X^q-1,(1+X)^q-1)=1$ in $\mathbb{Z}[X]$. Now, we prove the following lemma:

Lemma: If $f,g \in \mathbb{Z}[X]$ such that $gcd(f,g)=1 \implies$ for all sufficiently large prime $p$, $gcd(f,g)$ is a constant in $\mathbb{F}_p[X]$, i.e., $f,g$ don't share roots in $\mathbb{F}_p$.
Proof: By Bézout's Lemma, there is a constant $c \in \mathbb{Z}$ and $a,b \in \mathbb{Z}[X]$ such that $af+bg=c$, so if $p|f(r),g(r) \implies p|c$, so $p$ is bounded. $\square$

From the lemma, if $p$ is large enough, $(1+X)^q-1,X^q-1$ are coprime in $\mathbb{F}_p$, so since $|S|=q>N$, we are done.

$\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CyclicISLscelesTrapezoid
372 posts
#21 • 1 Y
Y by samrocksnature
Solved with v4913. This might seem like a problem about the structure of orders and primitive roots $\!\!\!\mod{p}$, but it's really a problem about polynomials.

We claim that for all primes $N$, there exists a sum-free multiplicative subgroup of size $N$.

Notice that if there exist integers $k$, $m$, and $n$ such that $\alpha^m+\alpha^n \equiv \alpha^k \pmod{p}$, then by scaling, there exist nonnnegative integers $m$ and $n$ such that $p \mid \alpha^m+\alpha^n-1$. Consider \[P(x)=\prod_{0 \le m,n < N}(x^m+x^n-1).\]We know that $x-1 \nmid P(x)$ because $P(1) \ne 0$ and $1+x+\cdots+x^{N-1} \nmid P(x)$ because $1+x+\cdots+x^{N-1} \nmid x^m+x^n-1$ for all $m$ and $n$ with $0 \le m,n < N$. Since $x-1$ and $1+x+\cdots+x^{N-1}$ are irreducible cyclotomic polynomials, we have $\gcd(P(x),x^N-1)=1$. By Bézout on integer polynomials, there exist integer polynomials $A(x)$ and $B(x)$ and a positive $c$ such that \[A(x)P(x)+B(x)(x^N-1)=c.\]
Now, we can construct. Choose $\alpha=4913c$ (the constant of $4913$ is just there so that $\alpha \ne 1$), and let $p$ be a prime dividing $\alpha^N-1$. Since $c \mid \alpha^N$, $p \nmid c$, so \[A(\alpha)P(\alpha) \equiv c \pmod{p} \Rightarrow p \nmid P(\alpha).\]That means $p \nmid \alpha^m+\alpha^n-1$ for all $m$ and $n$ with $0 \le m,n < N$, and we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8862 posts
#22
Y by
Fun problem. The key lemma is the following:

Lemma. If $f, g$ are relatively prime in $\mathbb Z[X]$, then for sufficiently large $p$, they are relatively prime in $\mathbb F_p[X]$ too.

Proof. By Bezout's lemma there exist polynomials $a, b \in \mathbb Q[X]$ such that $af+bg = 1$. On the other hand, pick $p$ greater than any denominator of a coefficient in $a$ or $b$. Suppose there exists $k$ such that $f(k) \equiv g(k) \equiv 0 \pmod p$; then $$\nu_p(af(k)+bg(k)) \geq 1 \neq 0$$which is an obvious contradiction. $\blacksquare$

Now the problem becomes quite clear. It suffices to find $p$ for which we can construct two polynomials $X^n - 1$ and $(1+X)^n - 1$ which share no roots in $\mathbb F_p$ for as large $n$ as we please. By the lemma, by picking $p$ large, it suffices for these to be relatively prime in $\mathbb Z[X]$.

On the other hand, construction for this is easy: just take $n = 2^m$ and notice that all $\Phi_{2^k}(X)$'s have distinct degree. On the other hand, by irreducibility $\Phi_{2^k}(X)$ and $\Phi_{2^k}(X+1)$ are irreducible. This yields infinitely many $n$, done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihategeo_1969
235 posts
#23
Y by
Now see that it is well known that all cyclotomic polynomials are irreducible and hence \[\gcd\left(\Phi_q(X),\Phi_q \left(X^N-1 \right) \right)=1\]where $q$ is any prime and $q \nmid N$. If not then one will find if $\omega$ is a $q^\text{th}$ root of unity, then so is $\omega^N-1$. And so is $\omega^2$ and so is $\omega^{2N}-1$ and hence so is $\omega^N+1$.

But $|\omega^N-1|=|\omega^N+1|=1 \implies \omega=0$.

And then by Bezout's lemma on polynomials we get that they are relatively prime polynomials over ${{\mathbb{F}}_p}$ for large enough $p$ $\left(\circledast \right)$. Now let

$\bullet$ $q \geq 5$ be a prime.
$\bullet$ Pick odd prime $p$ large enough according to $\circledast$ and further let $p \not \equiv \pm 1 \pmod {8}$

(basically $2$ is not a quadratic residue modulo $p$) and $p \mid \Phi_q(\alpha)$ such that $\nu_2(\alpha)=2$ and is a quadratic residue modulo $p$ (which obviously exists modulo any odd prime). See that one can pick such a prime $p$ exist due to our choice of $\alpha$ (obviously make sure $\alpha \not \equiv 1$).
\end{itemize}
See that construction and the key notes basically ensures that \[{\alpha}^q \equiv 1 \pmod p \text{ but } {\left(\alpha^N-1 \right)}^q \not \equiv 1 \pmod p\]because $p \nmid \Phi_q \left({\alpha}^N-1 \right)$ and hence we only need to ensure that $\alpha^N \not \equiv 2 \pmod p$ but this is true as $\alpha$ is a quadratic residue and $2$ is not modulo $p$.

And now one can easily see that the multiplicative subgroup $\{1,\alpha,\dots,{\alpha}^{q-1}\} \in {{\mathbb{F}}_p}$ is sum-free, and since $q$ is any arbitrarily large prime and the cardinality of the set is $q$, we win.
This post has been edited 4 times. Last edited by ihategeo_1969, Dec 5, 2024, 4:26 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EthanWYX2009
864 posts
#25 • 1 Y
Y by ys-lg
Take prime number $q>N.$ By Dirichlet Theorem take prime number $p\equiv 1\pmod q,$ let $p=mq+1.$ Take a primitive root $g$ in $\mathbb F_p,$ we prove $\{g^0,g^m,\ldots ,g^{m(q-1)}\}$ satisfies the condition. Here all "=" is under $\mathbb F_p.$ If $g^{mi}+g^{mj}=g^{mk}$ then $(g^{m(j-i)}+1)^q=g^{mkq}=1.$ Therefore $g^{m(j-i)}$ is root of $(x+1)^q-1=0$ and $x^q-1=0.$ Since $\gcd ((x+1)^q-1,x^q-1)=\gcd (x\Phi_q(x+1),(x-1)\Phi_q(x))=1.$ By Bezout Theorem there exists integer polynomial $A(x),B(x)$ and integer $d$ such that $A(x)[(x+1)^q-1]-B(x)(x^q-1)=d.$ So if we take $p>d$ we get contradiction. $\Box$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
john0512
4187 posts
#26
Y by
All statements in this solution assume that $p$ is sufficently large.

Suppose we fix $n$ and want a group of size $n$. The group will consist of the roots of $x^n-1\equiv 0\pmod{p}$. Because the elements can be expressed as $a^0,a^1,\dots$, no two summing to another is actually equivalent to no two being consecutive (as if $a^x+a^y=a^z$ then $1+a^{y-x}=a^{z-x}$). Thus, it suffices to show that there is no $x$ for which
$$x^n-1\equiv (x+1)^n-1\equiv 0\pmod{p}.$$
Claim: If $3\nmid n$, then $x^n-1$ and $(x+1)^n-1$ are coprime. We have $x^n-1=\prod_{d\mid n}\Phi_d(x)$ and $(x+1)^n-1=\prod_{d\mid n}\Phi_d(x+1)$.

Sub-claim: If $a$ and $b$ are positive integers such that $\Phi_a(x)=\Phi_b(x+1)$ for all $x$, then $a=3$ and $b=6$. If $\omega$ is a primitive $a$th root of unity, then $\omega+1$ is a primitive $b$th root of unity. There are only two ways to move right by $1$ and stay on the unit circle, both of which move from a $3$rd root of unity to a $6$th root of unity.

Thus, the only way $x^n-1$ and $(x+1)^n-1$ can share common factors is if the former has $\Phi_3(x)$ and the latter has $\Phi_6(x+1)$. Thus, choosing $3\nmid n$ avoids this.

Now, we show that arbitrarily large $n\not\equiv 0 \pmod{3}$ work. Because $x^n-1$ and $(x+1)^n-1$ are coprime in $\mathbb{Z}[x]$, we have that $\gcd(x^n-1,(x+1)^n-1)$ is upper bounded by a constant $C$ due to Euclidean algorithm. Picking $p>C$, we have that $x^n-1$ and $(x+1)^n-1$ are never both divisible by $p$, and further specifying $p\equiv 1\pmod{n}$ so that there is actually a group of order $n$ suffices.
This post has been edited 1 time. Last edited by john0512, Oct 21, 2024, 4:53 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ilikeminecraft
626 posts
#27
Y by
Let $q > N$ be a prime. Suppose $p\equiv1\pmod q.$ There exist infinitely many such $p$ due to dirichlet.

The second condition translates to $1 + \alpha^a=\alpha^b$ not having roots in terms of $a, b.$ Suppose $g$ is a primitive root modulo $p$ and $\operatorname{ord}_p(\alpha) = q = |S|.$ Then, the equation translates to $X^q - 1, (X - 1)^q - 1$ having no shared roots in $\mathbb F_p.$ It suffices to prove the following claim:

Claim: For sufficiently large $p,$ $X^q - 1, (X - 1)^q - 1$ have distinct roots in $\mathbb F_p.$
Proof: Clearly, if $q > 3,$ then $X^q - 1$ and $(X - 1)^q - 1$ have distince roots. Thus, by Bezouts lemma, there exists $a, b \in \mathbb Z[X]$ such that $a(X^q - 1) - b((X - 1)^q - 1) = d$ and $d \in\mathbb Z.$ Pick some $p > d$ and we are done.
Z K Y
N Quick Reply
G
H
=
a