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
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
Interesting inequalities
sqing   0
6 minutes ago
Source: Own
Let $ a,b>0 $ and $ a+b\leq 1  $ . Prove that
$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-k\left(\frac{a}{b}+\frac{b}{a}\right) \geq 225-2k$$Where $104\geq k\in N^+.$
$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right) \geq 225 $$$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-106\left(\frac{a}{b}+\frac{b}{a}\right) \geq \frac{155}{12}$$$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-108\left(\frac{a}{b}+\frac{b}{a}\right) \geq \frac{26}{3}$$$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-110\left(\frac{a}{b}+\frac{b}{a}\right) \geq \frac{17}{4}$$
0 replies
sqing
6 minutes ago
0 replies
R to R, with x+f(xy)=f(1+f(y))x
NicoN9   2
N 8 minutes ago by dangerousliri
Source: Own.
Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that\[
x+f(xy)=f(1+f(y))x
\]for all $x, y\in \mathbb{R}$.
2 replies
NicoN9
27 minutes ago
dangerousliri
8 minutes ago
Combi Geo
Adywastaken   2
N 32 minutes ago by lakshya2009
Source: NMTC 2024/8
A regular polygon with $100$ vertices is given. To each vertex, a natural number from the set $\{1,2,\dots,49\}$ is assigned. Prove that there are $4$ vertices $A, B, C, D$ such that if the numbers $a, b, c, d$ are assigned to them respectively, then $a+b=c+d$ and $ABCD$ is a parallelogram.
2 replies
Adywastaken
Yesterday at 3:58 PM
lakshya2009
32 minutes ago
Brilliant guessing game on triples
Assassino9931   1
N an hour ago by Sardor_lil
Source: Al-Khwarizmi Junior International Olympiad 2025 P8
There are $100$ cards on a table, flipped face down. Madina knows that on each card a single number is written and that the numbers are different integers from $1$ to $100$. In a move, Madina is allowed to choose any $3$ cards, and she is told a number that is written on one of the chosen cards, but not which specific card it is on. After several moves, Madina must determine the written numbers on as many cards as possible. What is the maximum number of cards Madina can ensure to determine?

Shubin Yakov, Russia
1 reply
Assassino9931
Yesterday at 9:46 AM
Sardor_lil
an hour ago
in n^2-9 has 6 positive divisors than GCD (n-3, n+3)=1
parmenides51   7
N an hour ago by AylyGayypow009
Source: Greece JBMO TST 2016 p3
Positive integer $n$ is such that number $n^2-9$ has exactly $6$ positive divisors. Prove that GCD $(n-3, n+3)=1$
7 replies
parmenides51
Apr 29, 2019
AylyGayypow009
an hour ago
Calculus
youochange   12
N an hour ago by FriendPotato
Find the area enclosed by the curves $e^x,e^{-x},x^2+y^2=1$
12 replies
youochange
Yesterday at 2:38 PM
FriendPotato
an hour ago
The familiar right angle from the orthocenter
buratinogigle   2
N an hour ago by jainam_luniya
Source: Own, HSGSO P6
Let $ABC$ be a triangle inscribed in a circle $\omega$ with orthocenter $H$ and altitude $BE$. Let $M$ be the midpoint of $AH$. Line $BM$ meets $\omega$ again at $P$. Line $PE$ meets $\omega$ again at $Q$. Let $K$ be the orthogonal projection of $E$ on the line $BC$. Line $QK$ meets $\omega$ again at $G$. Prove that $GA\perp GH$.
2 replies
buratinogigle
4 hours ago
jainam_luniya
an hour ago
a deep thinking topic. either useless or extraordinary , not yet disovered
jainam_luniya   5
N an hour ago by jainam_luniya
Source: 1.99999999999....................................................................1. it this possible or not we can debate
it can be a new discovery in world or NT
5 replies
jainam_luniya
an hour ago
jainam_luniya
an hour ago
Divisibilty...
Sadigly   4
N an hour ago by jainam_luniya
Source: Azerbaijan Junior NMO 2025 P2
Find all $4$ consecutive even numbers, such that the sum of their squares divides the square of their product.
4 replies
1 viewing
Sadigly
Yesterday at 9:07 PM
jainam_luniya
an hour ago
ioqm to imo journey
jainam_luniya   2
N an hour ago by jainam_luniya
only imginative ones are alloud .all country and classes or even colleges
2 replies
jainam_luniya
2 hours ago
jainam_luniya
an hour ago
Inequality
Sadigly   5
N an hour ago by jainam_luniya
Source: Azerbaijan Junior MO 2025 P5
For positive real numbers $x;y;z$ satisfying $0<x,y,z<2$, find the biggest value the following equation could acquire:


$$(2x-yz)(2y-zx)(2z-xy)$$
5 replies
Sadigly
May 9, 2025
jainam_luniya
an hour ago
D'B, E'C and l are congruence.
cronus119   7
N 2 hours ago by Tkn
Source: 2022 Iran second round mathematical Olympiad P1
Let $E$ and $F$ on $AC$ and $AB$ respectively in $\triangle ABC$ such that $DE || BC$ then draw line $l$ through $A$ such that $l || BC$ let $D'$ and $E'$ reflection of $D$ and $E$ to $l$ respectively prove that $D'B, E'C$ and $l$ are congruence.
7 replies
cronus119
May 22, 2022
Tkn
2 hours ago
a set of $9$ distinct integers
N.T.TUAN   17
N 2 hours ago by hlminh
Source: APMO 2007
Let $S$ be a set of $9$ distinct integers all of whose prime factors are at most $3.$ Prove that $S$ contains $3$ distinct integers such that their product is a perfect cube.
17 replies
N.T.TUAN
Mar 31, 2007
hlminh
2 hours ago
Asymmetric FE
sman96   13
N 2 hours ago by youochange
Source: BdMO 2025 Higher Secondary P8
Find all functions $f: \mathbb{R} \to \mathbb{R}$ such that$$f(xf(y)-y) + f(xy-x) + f(x+y) = 2xy$$for all $x, y \in \mathbb{R}$.
13 replies
sman96
Feb 8, 2025
youochange
2 hours ago
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
8863 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
627 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