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
Geometry
Lukariman   8
N 7 minutes ago by Lukariman
Given circle (O) and point P outside (O). From P draw tangents PA and PB to (O) with contact points A, B. On the opposite ray of ray BP, take point M. The circle circumscribing triangle APM intersects (O) at the second point D. Let H be the projection of B on AM. Prove that $\angle HDM$ = 2∠AMP.
8 replies
Lukariman
Tuesday at 12:43 PM
Lukariman
7 minutes ago
Linear colorings mod 2^n
vincentwant   1
N 8 minutes ago by vincentwant
Let $n$ be a positive integer. The ordered pairs $(x,y)$ where $x,y$ are integers in $[0,2^n)$ are each labeled with a positive integer less than or equal to $2^n$ such that every label is used exactly $2^n$ times and there exist integers $a_1,a_2,\dots,a_{2^n}$ and $b_1,b_2,\dots,b_{2^n}$ such that the following property holds: For any two lattice points $(x_1,y_1)$ and $(x_2,y_2)$ that are both labeled $t$, there exists an integer $k$ such that $x_2-x_1-ka_t$ and $y_2-y_1-kb_t$ are both divisible by $2^n$. How many such labelings exist?
1 reply
vincentwant
Apr 30, 2025
vincentwant
8 minutes ago
sqrt(n) or n+p (Generalized 2017 IMO/1)
vincentwant   1
N 9 minutes ago by vincentwant
Let $p$ be an odd prime. Define $f(n)$ over the positive integers as follows:
$$f(n)=\begin{cases}
\sqrt{n}&\text{ if n is a perfect square} \\
n+p&\text{ otherwise}
\end{cases}$$
Let $p$ be chosen such that there exists an ordered pair of positive integers $(n,k)$ where $n>1,p\nmid n$ such that $f^k(n)=n$. Prove that there exists at least three integers $i$ such that $1\leq i\leq k$ and $f^i(n)$ is a perfect square.
1 reply
vincentwant
Apr 30, 2025
vincentwant
9 minutes ago
Flight between cities
USJL   5
N 22 minutes ago by Photaesthesia
Source: 2025 Taiwan TST Round 1 Mock P5
A country has 2025 cites, with some pairs of cities having bidirectional flight routes between them. For any pair of the cities, the flight route between them must be operated by one of the companies $X, Y$ or $Z$. To avoid unfairly favoring specific company, the regulation ensures that if there have three cities $A, B$ and $C$, with flight routes $A \leftrightarrow B$ and $A \leftrightarrow C$ operated by two different companies, then there must exist flight route $B \leftrightarrow C$ operated by the third company different from $A \leftrightarrow B$ and $A \leftrightarrow C$ .

Let $n_X$, $n_Y$ and $n_Z$ denote the number of flight routes operated by companies $X, Y$ and $Z$, respectively. It is known that, starting from a city, we can arrive any other city through a series of flight routes (not necessary operated by the same company). Find the minimum possible value of $\max(n_X, n_Y , n_Z)$.

Proposed by usjl and YaWNeeT
5 replies
USJL
Mar 8, 2025
Photaesthesia
22 minutes ago
A problem from Le Anh Vinh book.
minhquannguyen   0
28 minutes ago
Source: LE ANH VINH, DINH HUONG BOI DUONG HOC SINH NANG KHIEU TOAN TAP 1 DAI SO
Let $n$ is a positive integer. Determine all functions $f:(1,+\infty)\to\mathbb{R}$ such that
\[f(x^{n+1}+y^{n+1})=x^nf(x)+y^nf(y),\forall x,y>1.\]
0 replies
minhquannguyen
28 minutes ago
0 replies
IMO ShortList 1999, algebra problem 1
orl   42
N an hour ago by ihategeo_1969
Source: IMO ShortList 1999, algebra problem 1
Let $n \geq 2$ be a fixed integer. Find the least constant $C$ such the inequality

\[\sum_{i<j} x_{i}x_{j} \left(x^{2}_{i}+x^{2}_{j} \right) \leq C
\left(\sum_{i}x_{i} \right)^4\]

holds for any $x_{1}, \ldots ,x_{n} \geq 0$ (the sum on the left consists of $\binom{n}{2}$ summands). For this constant $C$, characterize the instances of equality.
42 replies
orl
Nov 13, 2004
ihategeo_1969
an hour ago
q(x) to be the product of all primes less than p(x)
orl   19
N an hour ago by ihategeo_1969
Source: IMO Shortlist 1995, S3
For an integer $x \geq 1$, let $p(x)$ be the least prime that does not divide $x$, and define $q(x)$ to be the product of all primes less than $p(x)$. In particular, $p(1) = 2.$ For $x$ having $p(x) = 2$, define $q(x) = 1$. Consider the sequence $x_0, x_1, x_2, \ldots$ defined by $x_0 = 1$ and \[ x_{n+1} = \frac{x_n p(x_n)}{q(x_n)} \] for $n \geq 0$. Find all $n$ such that $x_n = 1995$.
19 replies
orl
Aug 10, 2008
ihategeo_1969
an hour ago
Interesting inequality
sealight2107   2
N 2 hours ago by arqady
Source: Own
Let $a,b,c>0$ such that $a+b+c=3$. Find the minimum value of:
$Q=\frac{a}{b}+\frac{b}{c}+\frac{c}{a}+\frac{1}{a^3+b^3+abc}+\frac{1}{b^3+c^3+abc}+\frac{1}{c^3+a^3+abc}$
2 replies
sealight2107
Tuesday at 4:53 PM
arqady
2 hours ago
Cyclic Quads and Parallel Lines
gracemoon124   16
N 3 hours ago by ohiorizzler1434
Source: 2015 British Mathematical Olympiad?
Let $ABCD$ be a cyclic quadrilateral. Let $F$ be the midpoint of the arc $AB$ of its circumcircle which does not contain $C$ or $D$. Let the lines $DF$ and $AC$ meet at $P$ and the lines $CF$ and $BD$ meet at $Q$. Prove that the lines $PQ$ and $AB$ are parallel.
16 replies
gracemoon124
Aug 16, 2023
ohiorizzler1434
3 hours ago
Radical Center on the Euler Line (USEMO 2020/3)
franzliszt   37
N 4 hours ago by Ilikeminecraft
Source: USEMO 2020/3
Let $ABC$ be an acute triangle with circumcenter $O$ and orthocenter $H$. Let $\Gamma$ denote the circumcircle of triangle $ABC$, and $N$ the midpoint of $OH$. The tangents to $\Gamma$ at $B$ and $C$, and the line through $H$ perpendicular to line $AN$, determine a triangle whose circumcircle we denote by $\omega_A$. Define $\omega_B$ and $\omega_C$ similarly.
Prove that the common chords of $\omega_A$,$\omega_B$ and $\omega_C$ are concurrent on line $OH$.

Proposed by Anant Mudgal
37 replies
franzliszt
Oct 24, 2020
Ilikeminecraft
4 hours ago
Functional equation with powers
tapir1729   13
N 4 hours ago by ihategeo_1969
Source: TSTST 2024, problem 6
Determine whether there exists a function $f: \mathbb{Z}_{> 0} \rightarrow \mathbb{Z}_{> 0}$ such that for all positive integers $m$ and $n$,
\[f(m+nf(m))=f(n)^m+2024! \cdot m.\]Jaedon Whyte
13 replies
tapir1729
Jun 24, 2024
ihategeo_1969
4 hours ago
Powers of a Prime
numbertheorist17   34
N 4 hours ago by KevinYang2.71
Source: USA TSTST 2014, Problem 6
Suppose we have distinct positive integers $a, b, c, d$, and an odd prime $p$ not dividing any of them, and an integer $M$ such that if one considers the infinite sequence \begin{align*}
		ca &- db \\
		ca^2 &- db^2 \\
		ca^3 &- db^3 \\
		ca^4 &- db^4 \\
&\vdots
	\end{align*} and looks at the highest power of $p$ that divides each of them, these powers are not all zero, and are all at most $M$. Prove that there exists some $T$ (which may depend on $a,b,c,d,p,M$) such that whenever $p$ divides an element of this sequence, the maximum power of $p$ that divides that element is exactly $p^T$.
34 replies
numbertheorist17
Jul 16, 2014
KevinYang2.71
4 hours ago
IMO 2018 Problem 5
orthocentre   80
N 5 hours ago by OronSH
Source: IMO 2018
Let $a_1$, $a_2$, $\ldots$ be an infinite sequence of positive integers. Suppose that there is an integer $N > 1$ such that, for each $n \geq N$, the number
$$\frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}$$is an integer. Prove that there is a positive integer $M$ such that $a_m = a_{m+1}$ for all $m \geq M$.

Proposed by Bayarmagnai Gombodorj, Mongolia
80 replies
orthocentre
Jul 10, 2018
OronSH
5 hours ago
Line passes through fixed point, as point varies
Jalil_Huseynov   60
N 5 hours ago by Rayvhs
Source: APMO 2022 P2
Let $ABC$ be a right triangle with $\angle B=90^{\circ}$. Point $D$ lies on the line $CB$ such that $B$ is between $D$ and $C$. Let $E$ be the midpoint of $AD$ and let $F$ be the seconf intersection point of the circumcircle of $\triangle ACD$ and the circumcircle of $\triangle BDE$. Prove that as $D$ varies, the line $EF$ passes through a fixed point.
60 replies
Jalil_Huseynov
May 17, 2022
Rayvhs
5 hours ago
USAMO 2001 Problem 5
MithsApprentice   23
N Apr 25, 2025 by Ilikeminecraft
Let $S$ be a set of integers (not necessarily positive) such that

(a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$;
(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$.

Prove that $S$ is the set of all integers.
23 replies
MithsApprentice
Sep 30, 2005
Ilikeminecraft
Apr 25, 2025
USAMO 2001 Problem 5
G H J
G H BBookmark kLocked kLocked NReply
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MithsApprentice
2390 posts
#1 • 3 Y
Y by Davi-8191, Adventure10, Mango247
Let $S$ be a set of integers (not necessarily positive) such that

(a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$;
(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$.

Prove that $S$ is the set of all integers.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MithsApprentice
2390 posts
#2 • 1 Y
Y by Adventure10
When replying to the problem, I ask that you make posts for solutions and submit comments, jokes, smilies, etc. separately. Furthermore, please do not "hide" any portion of the solution. Please use LaTeX for posting solutions. Thanks.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mustafa
580 posts
#3 • 2 Y
Y by Adventure10, Mango247
Sorry to bump up such an old topic, but does anyone have a solution to this?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mstoenescu
316 posts
#4 • 2 Y
Y by Adventure10, Mango247
Look at http://www.kalva.demon.co.uk/usa/usoln/usol015.html :roll:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cuopbientcd
169 posts
#5 • 1 Y
Y by Adventure10
I read it and I feel Math be beautyful!I am happy! :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Zhero
2043 posts
#6 • 13 Y
Y by QuocBao, Nguyenhuyhoang, SMOJ, huynguyen, r31415, guptaamitu1, mijail, Adventure10, Mango247, and 4 other users
Let $c = a^2 - b$ and $d = b^2 - a$. We claim that $\gcd(a^2 - b^2, a^2 - c^2, b^2 - d^2) = 1$. Assume to the contrary that this is false. Then we can find some prime $p$ such that $a^2 \equiv b^2 \pmod{p}$, $a^2 - b \equiv \pm a \pmod{p}$, and $b^2 - a \equiv \pm a \pmod{p}$. Since $p | a^2 - b^2$, $p | a$ if and only if $p | b$; since $\gcd(a,b) = 1$, $p$ divides neither $a$ nor $b$. From $b^2 \equiv a^2 \equiv b \pm a$, $b^2 \equiv 0 \pmod{p}$ or $b^2 \equiv 2b \pmod{p}$. Since $p \not | b$, $p | b-2$. Similarly,$p | a-2$, which contradicts $\gcd(a-2, b-2) = 1$.

Let $z = a$. We note that for any $x,y$ in $S$, $y^2 - z$ must be in $S$, so $x^2 - (y^2 - z) = (x^2 - y^2) + z$ must be in $S$. It follows that for all $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$ in $S$, $z + \sum_{i=1}^n (x_i^2 - y_i^2) \in S$. Hence, for all positive integers $A$, $B$, and $C$, $z + A(a^2 - b^2) + B(a^2 - c^2) + C(b^2 - d^2) \in S$. As $\gcd(a^2 - b^2, a^2 - c^2, b^2 - d^2) = 1$, the Frobenius coin problem tells us that all sufficiently large positive integers lie in $S$. In other words, for some positive integer $M$, all integers larger than or equal to $M$ lie in $S$. We may suppose without loss of generality that $M \geq 2$.

Let $k$ be any integer less than $M$. Since $(M+1)^2 - k > (M+1)^2 - M > M$ (from $M \geq 2$) and $M+1 > M$, $(M+1)^2 - k$ and $M+1$ lie in $S$, whence $(M+1)^2 - ((M+1)^2 - k) = k$ must lie in $S$ as well. Thus, $S = \mathbb{Z}$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jatin
547 posts
#7 • 2 Y
Y by Adventure10, Mango247
The official solution is given here.

I have a doubt in it.

In the last line of the first paragraph of the solution, it is said that
\[m=\gcd \{c^2-d^2:c,d\in S\} \]
But if $S$ is infinite, as it later turns out to be, $m$ is not well defined.
In fact, $m$ may be a supernatural number. (http://en.wikipedia.org/wiki/Supernatural_numbers)
So for this argument to work, I think that $S$ must be assumed to be finite.

Could someone kindly clarify this?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Zhero
2043 posts
#8 • 2 Y
Y by Adventure10, Mango247
I don't see why $m$ would not be well-defined. The $\gcd$ of an infinite set of integers is perfectly well-defined; it is the largest integer that divides every element of the set. In your case, if you let $s$ be any nonzero element of $\{c^2 - d^2 : c, d \in S\}$, you must have $m \leq |s|$, so $m$ is certainly finite.
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
#9 • 8 Y
Y by anantmudgal09, vsathiam, Delray, mmathss, v4913, mijail, Kobayashi, Adventure10
Call an integer $d > 0$ shifty if $S = S+d$ (meaning $S$ is invariant under shifting by $d$).

First, note that if $u, v \in S$, then for any $x \in S$, \[ v^2 - (u^2-x) = (v^2-u^2) + x \in S. \]Since we can easily check that $|S| > 1$ and $S \neq \{n, -n\}$ we conclude exists a shifty integer.

Now we contend that $1$ is shifty. Assume for contradiction not. Then for GCD reasons the set of shifty integers must be $d {\mathbb Z}$ for some $d > 2$.

So it follows that \[ S \subseteq \left\{ x : x^2 \equiv m \pmod d \right\} \]for some fixed $m$, since otherwise if we take any $p,q \in S$ with distinct squares modulo $d$, then $q^2-p^2 \not\equiv 0 \pmod d$ is shifty, which is impossible.

Now take $a,b \in S$ as in (a). In that case we need to have \[ a^2 \equiv b^2 \equiv (a^2-a)^2 \equiv (b^2-b)^2 \pmod d. \]Passing to a prime $p \mid d$, we have the following:
  • Since $a^2 \equiv (a^2-a)^2 \pmod p$ or equivalently $a^3(a-2) \equiv 0 \pmod p$, either $a \equiv 0 \pmod p$ or $a \equiv 2 \pmod p$.
  • Similarly, either $b \equiv 0 \pmod p$ or $b \equiv 2 \pmod p$.
  • Since $a^2 \equiv b^2 \pmod p$, or $a \equiv \pm b \pmod p$, we find either $a \equiv b \equiv 0 \pmod p$ or $a \equiv b \equiv 2 \pmod p$ (even if $p=2$).
This is a contradiction.

Remark: The condition (a) cannot be dropped, since otherwise we may take $S = \left\{ 2 \pmod p \right\}$ or $S = \left\{ 0 \pmod p \right\}$, say.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yunseo
163 posts
#11 • 1 Y
Y by Adventure10
For any elements x, y, z that are in S, we know that $(x^2-y^2)$ + z is in S. Thus, we wish to show that we can create all residues $\mod a^2 - b^2$ where a, b are elements given in condition 1.

We then show that $a$, $b$, $a^2-a$, $b^2-b$ are all distinct mod $a^2-b^2$. Then, we show that $(a^2-a)^2-(b^2-b)^2 \not\equiv 0 \mod a^2-b^2$. Since for any elements x, y, z that are in S, we know that $(x^2-y^2)$ + z, let $x = a^2-a $ and $y= b^2-b$ and we can span through all the residues.
This post has been edited 1 time. Last edited by yunseo, May 1, 2019, 11:34 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pad
1671 posts
#12
Y by
Suppose we have some $m,n\in S$. Then
\[ x\in S\implies m^2-x \in S \implies n^2-(m^2-x)=x + (n^2-m^2) \in S. \]Therefore, it suffices to show that we can get any residue mod $a^2-b^2$. From now on, we work fully in mod $a^2-b^2$.

From just $\{a,b\}$, we can get $\{a^2-a,a^2-b,b^2-a,b^2-b\}$, which is equivalent to just $\{a^2-a, b^2-b\}$ mod $a^2-b^2$. Therefore, if $x\in S$, then we can also get $x$ plus the difference of two elements of $\{a^2, b^2, (a^2-a)^2, (b^2-b)^2\}$ in $S$. Now, it suffices to show that we cannot have
\[ a^2 \equiv b^2 \equiv (a^2-a)^2 \equiv (b^2-b)^2 \pmod{p} \qquad (\clubsuit)\]for a prime $p$, because if this were the case, then any new element we add can only be a multiple of $p$ greater; hence we will not get all possible residues. Otherwise, we will get a difference which is relatively prime to $a^2-b^2$, and then we can add this difference over and over to $x$ to generate all possible residues.

Suppose $(\clubsuit)$ holds. All equivalences are in mod $p$. Then $p\mid (a^2-a)^2-a^2=a^3(a-2)$, so $a\equiv 0$ or $a\equiv 2$. Similarly $b\equiv 0$ or $b\equiv 2$. But $a^2\equiv b^2$, so $a \equiv \pm b$. Therefore, either $a\equiv b \equiv 2 \pmod p$ or $a\equiv b \pmod p$. But neither of these are possible by condition (a)! Contradiction. This completes the proof.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
alexiaslexia
110 posts
#13 • 2 Y
Y by yayups, ATGY
A double (or triple, depending on how you word it) Euclidean Algorithm.
Using the condition $(a,b) = 1$ is easy enough, however $(a-2,b-2) = 1$ won't be used $\textit{unless you've come up with the thing.}$

$\color{green} \rule{25cm}{2pt}$
$\color{green} \textbf{A Simple Way to Look at It.}$ Let $x,y \in S$. Then, for every $s \in S$,
\[ s+ (y^2-x^2) \in S; \quad s+(x^2-y^2) = s- (y^2-x^2) \in S \]This will imply the fact that
\[ S = S+(y^2-x^2) \ \forall x,y \in S \]$\color{green} \rule{25cm}{0.4pt}$
$\color{green} \textbf{Proof 1.}$ The Main Point of the Problem (and what makes this a 25+ MOHS.)

If $s \in S$, then $x^2-s \in S$. We'll apply this again with $y$ instead of $x$: as $x^2-s \in S$, so
\[ y^2- (x^2-s) \in S \]validating the Claim. $\blacksquare$ $\blacksquare$

Magical Transformation?

$\color{red} \rule{25cm}{2pt}$
$\color{red} \textbf{Making the set} \ S \ \textbf{behave like} \ \mathbb{Z} \  \textbf{by compressing the shift into} \ 1.$ Let $s \in S$. Then,
\[ s+1 \in S\](such a simple Claim, is it not?)
$\color{red} \rule{25cm}{0.4pt}$
$\color{red} \textbf{Proof 2.}$ This is multiple (tedious) applications of $\color{green} \textbf{A Simple Way to Look at It}$ (the tedious-ness of this does in fact contribute on why this is my favorite NT problem among my recent sessions. See $(\bigstar \bigstar)$ for further exposition.)

Firstly,
we can easily infer that given $a,b$ in the problem statement, $a^2-b$ and $b^2-a$ are elements of $S$.
Secondly,
We see that
\[ \{b^2-a^2, (a^2-b)^2-b^2, (b^2-a)^2-a^2\} \in \{s_2^2-s_1^2 \mid \ \text{for} \ s_1,s_2 \in S\} \]and we can infer from $\color{green} \textbf{A Simple Way to Look at It}$ that
\[ S = S+z \cdot (b^2-a^2); \ S = S+z \cdot (a^2)(a^2-2b); \ S = S+z \cdot (b^2)(b^2-2a) \]for every $z \in \mathbb{Z}$.

Thirdly,
as $S = S+d_1 = S+d_2$ implies $S = S+\gcd(d_1,d_2)$ by $\textbf{Euclid}$/$\textbf{Bezout}$/$\textit{just repeat the iteration till you get the smallest number}$.
Since
\[ \gcd(b^2-a^2,a^2(a^2-2b)) = \gcd(b+a,a^2-2b) = g_1 \]applying the above statement with $d_1 = b^2-a^2$ and $d_2 = a^2(a^2-2b)$ yields
\[ S = S+g_1 \]and similarly with $\gcd(b+a,b^2-2a) = g_2$, we get
\[ S = S+g_1=S+g_2 \]
Fourthly,
$g_1$ and $g_2$ are prime targets to apply the Lemma in Thirdly (I purposefully avoided another $d$ as a placeholder variable for the transitional $\text{gcd}$, instead I picked $g$ from $\textbf{g}cd$.)

If $\gcd(g_1,g_2) = 1$, our job is done. To prove that, suppose $p \mid g_1, p \mid g_2$ for $p$ prime. Then,
\[ p \mid a+b, p \mid a^2-2b \Rightarrow p \mid a^2+2a, b^2-2b. \]This may not seem like much, but that's the usefulness of having more than one $g_i$s! Doing the same for the other expression,
\[ p \mid a^2-2a, b^2+2b. \]Substracting yields $p \mid 4a, p \mid 4b$ --- which means either $p = 2$ and $a,b$ even or $p \mid a,b$ which is impossible as $(a,b) = 1$. $\blacksquare$ $\blacksquare$ $\blacksquare$

Note that we did use the condition $(a-2,b-2) = 1$ explicitly to prove the $\gcd$ computation in Thirdly.

Motivation: Replicating the Legendary Euclids, with two bases and Hensels.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GeronimoStilton
1521 posts
#14
Y by
Observation: There are at least two elements $c,d\in S$ with $|c|\ne |d|$.

Proof: If the $a,b$ have $|a|\ne |b|$ we are done. Otherwise $a,b$ are both $\pm1$, so taking $a^2-b$ implies the desired.

Now, for any $c,d\in S$ with $|c|\ne |d|$, note $\forall t\in S$, $c^2-(d^2-t)=c^2-d^2+t\in S$. Thus $k(c^2-d^2)+t\in S$ for all integers $k$ by this argument. Such observations imply that $S$ consists of a set of residues modulo some integer $d\ne0$. Let $d>0$ and $d$ be minimal. For any $a,b$, we claim $a^2\equiv b^2\pmod{d}$. This is because we must have $d\mid a^2-b^2$ by the minimality of $d$. We claim $d=1$, which suffices. Otherwise, let $p\mid d$ be prime. Let $a,b$ be the given relatively prime elements of $S$. Then $p\mid a^2-b^2$ implies that at least one of $p\mid a-b$ and $p\mid a+b$ holds. Since $a$ and $b$ are relatively prime, we cannot have $p\mid a$. Note that all elements of $S$ are $\pm a$ modulo $p$. Then we have $a^2-a$ is one of $a$ and $-a$ modulo $p$. The second case is clearly bad, so $a^2-a\equiv a\pmod{p}\implies a^2\equiv 2a\pmod{p}\implies a\equiv 2\pmod{p}$. Similarly $b\equiv 2\pmod{p}$, which contradicts the given, 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.
nbdaaa
347 posts
#15
Y by
Bezout Lemma
Claim 1: $1 \in S$.
Suppose $a,b,c \in S$, then from $2$ we get $(a^2-b^2)+c \in S$. Then by induction we have $c+(a^2-b^2)n \in S$ for $n \in Z$ (*)
Let $A=a^2-b^2$,$B=(a^2-a)^2-a^2$ and $C=(b^2-b)^2-b^2$
Then from the conclusion in (*), we have $c +xA+yB+zC \in S$. Suppose that $d=gcd(A,B,C) >1$ then there exists $p \mid d$ such that $p \mid A,B,C$
\[ \Leftrightarrow \left\{ \begin{array}{l}
p \mid {a^2} - {b^2}\\
p \mid {({a^2} - a)^2} - {a^2}\\
p \mid{({b^2} - b)^2} - {b^2}
\end{array} \right. \Leftrightarrow \left\{ \begin{array}{l}
\left[ \begin{array}{l}
p \mid a - b\\
p \mid a + b
\end{array} \right.\\
\left[ \begin{array}{l}
p \mid {a^2} - 2a\\
p \mid {a^2}
\end{array} \right.\\
\left[ \begin{array}{l}
p \mid {b^2} - 2b\\
p \mid {b^2}
\end{array} \right.
\end{array} \right.\]But all the cases can happen will lead to a contradiction that $(a,b)=(a-2,b-2)=1$.
Thus $gcd(A,B,C)=1$, then there exists $x,y,z$ such that $xA+yB+zC=1-c$ by Bezout Lemma
Then $c+xA+yB+zC=c+1-c=1 \in S$
Claim 2 : All the integers are in $S$
From $1 \in S$, we lead to $0 \in S,-1 \in S, 2 \in S, -2 \in S$. We will show the claim by induction
Suppose that all $|m| \le n$ are in $S$
Consider $n+1$
  • If $n+1=t^2$ then $t <n$ and from induction, $t \in S \Rightarrow t^2-0=t^2=n+1 \in S$
  • If $n+1$ is not a perfect square, let it be $n+1=t^2+m$ for $ 0< m < 2t+1$ (Since $t^2 <n+1 <(t+1)^2$)
    Then $0<m<2t+1<t^2<n$, means $m \in S \Rightarrow -m \in S$ and $t \in S$ from induction, then $t^2-(-m)=t^2+m=n+1 \in S$ and done!!!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DottedCaculator
7348 posts
#16
Y by
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
guptaamitu1
656 posts
#17 • 1 Y
Y by mijail
Claim: For any prime $p$, all residues modulo $p$ are in $S$.

First Proof: FTSOC $\{a_1,\ldots,a_k\}$ are the only residues in $S$ with $k < p$. Then for any $i$ we must have $\{a_i^2 - a_1,\ldots,a_i^2 - a_k \} \equiv \{a_1,\ldots,a_k\}$. Summing $ka_i^2$ is same for each $i$. As $\gcd(k,p)= 1$, so $a_1^2 \equiv \cdots \equiv a_k^2$. Thus $k \le 2$ and $p \mid a_1 + a_k$ (if $k = 2$). Now $a_1^2 - a_1 \in \{a_1,a_k\}$. If $k \ge 2$, then $a_1^2 \equiv 0$, forcing $a_1 \equiv a_k \equiv 0$, contradicting $k \ge 2$. Thus $k=1$ and $a_1^2 - a_1 \equiv a_1$. Then $a_1 \in \{0,2\}$. But then for any $a,b \in S$, either $p \mid \gcd(a,b)$ or $p \mid \gcd(a-2,b-2)$, contradiction. $\square$

Second Proof: Consider sets $\{a_1^2,\ldots,a_k^2\}$ and $\{-a_1,\ldots,-a_k\}$. By Cauchy-Davenport there $\oplus$ has cardinality at least $2k-1$. But also there $\oplus$ is subset of $\{a_1,\ldots,a_k\}$. This forces $k=1$. We can finish as before. $\square$


Claim: For any $n \in \mathbb Z_{>0}$, all residues modulo $n$ are in $S$.

Proof: This is similar to previous, but we have to be a little more clever. FTSOC $\{a_1,\ldots,a_k\}$ are only residues modulo $S$ with $k < n$. Pick a prime $p$ dividing $\frac{n}{\gcd(k,n)}$. As before all $ka_i^2$ are congruent modulo $n$. Thus each $a_i^2$ are congruent modulo $p$. This basically means for any $a \in S$, $a^2$ is same modulo $p$ for any choice of $a$. But by previous claim, we know the residues $0,1$ are in $S$ (modulo $p$), forcing $0^2 \equiv 1^2$ mod $p$, contradiction. $\square$


Now fix any $m,n \in S$. Let $T = m^2 - n^2$. We Claim that
$$Tk-y \in S ~~ \forall ~ y \in S, k \in \mathbb Z \qquad \qquad (1)$$This follows by fixing $y$ and using induction on $T$ (by using (b) two times for $x=m,n$ or $x=n,m$). By our Claim, $y$ can be anything modulo $T$, hence $S = \mathbb Z$. $\blacksquare$

Motivation
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5001 posts
#18
Y by
Inspired by ELMO 2019/5, after getting this (note the condition $d>0$ is dropped):
v_Enhance wrote:
Call an integer $d \neq 0$ shifty if $S = S+d$ (meaning $S$ is invariant under shifting by $d$).

First, note that if $u, v \in S$, then for any $x \in S$, \[ v^2 - (u^2-x) = (v^2-u^2) + x \in S. \]Since we can easily check that $|S| > 1$ and $S \neq \{n, -n\}$ we conclude exists a shifty integer.

and noting that if $d$ is shifty then $-d$ is as well (by swapping $u,v$), here is another solution. It's not as efficient but the idea is basically a carbon copy of the technique used in the ELMO problem and I think it's pretty neat:

The key claim is that $S$ covers all residues modulo $p^n$ for any prime $p$ and $n \geq 1$. Surprisingly, most of the work is to prove this for $n=1$. Let $n=1$, and let $S_p=\{a_1,\ldots,a_k\}$ be the set of residues modulo $p$ of $S$, so we want to prove that $k=p$. Suppose otherwise, and fix $1 \leq i \leq k$, so $a_i^2-a_j \in S_p$ for all $1 \leq j \leq k$. As $j$ varies these are all distinct, hence
$$\{a_i^2-a_1,\ldots,a_i^2-a_k\} \equiv \{a_1,\ldots,a_k\} \pmod{p}.$$Summing both sides, this means that
$$ka_i^2-(a_1+\cdots+a_k) \equiv a_1+\cdots+a_k \pmod{p} \implies a_i^2 \equiv \frac{2(a_1+\cdots+a_k)}{k} \pmod{p}$$as $p \nmid k$. Hence it follows that $a_i^2$ is constant, so $k=1,2$.
  • If $k=1$, then we have $a_1^2-a_1 \equiv a_1 \pmod{p}$, so $a_1 \equiv 0,2 \pmod{p}$. But then $p$ either divides $\gcd(a,b)$ or $\gcd(a-2,b-2)$ for all $a,b \in S$, violating the first condition.
  • If $k=2$, then we have $a_1\equiv -a_2\pmod{p}$. But then $a_1+\cdots+a_k \equiv 0 \pmod{p}$, so $a_1^2 \equiv a_2^2=0$, which is a contradiction.
It follows that $k=p$. Now, to extend to $p^n$, the same "sum argument" applied to the set of residues $\pmod{p^n}$, which we will define as $\{a_1,\ldots,a_K\}$, implies that
$$Ka_i^2 \equiv 2(a_1+\cdots+a_K) \pmod{p^n}$$for all $1 \leq i \leq K$. But there exists $i,j$ such that $p \mid a_i$ but $p \nmid a_j$ by the $n=1$ case, so if $p^n \nmid K$ then $\nu_p(Ka_j^2)<n,\nu_p(Ka_i^2)$, hence we cannot have $Ka_i^2 \equiv Ka_j^2 \pmod{p^n}$. It follows that $p^n \mid K \implies K=p^n$.

To finish, note that by Chinese Remainder Theorem we can show that for any shifty $d>0$, $S$ forms a complete residue set $\pmod{d}$. Then $d$ and $-d$ are shifty, so it follows that $S$ covers all of $\mathbb{Z}$, as desired. $\blacksquare$
This post has been edited 1 time. Last edited by IAmTheHazard, Mar 24, 2022, 8:51 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1714 posts
#19
Y by
If $a,b\in S$ then for any $c\in S$ we have $a^2-c\in S$ and thus $b^2-(a^2-c)=(b^2-a^2)+c\in S.$ Now, if we let $P=\{a^2-b^2 \mid a,b\in S\}$ then for any $x\in P$ we have $c\in S\implies c+kx\in P$ for any integer $k$. Therefore, if we find $x,y,z\in P$ such that $\gcd(x,y,z)=1$ then we are done by Bezout's. Suppose
\begin{align*}
p &\mid a^2-b^2 \\
p &\mid (a^2-b)^2-a^2 \\
p &\mid (b^2-a)-b^2
\end{align*}Then the second plus the first is $p \mid a^4-2a^2b$. Since $\gcd(a,b)=1$ we have $p\mid a^2-2b.$ Similarly, $p\mid b^2-2a$ so $p\mid a^2-b^2+2a-2b\implies p\mid 2(a-b).$ If $p=2$ then $a,b$ odd which violates the second one. Now, $p\mid a-b$ so we can switch any $a$ with $b$ to get from the second one $p\mid a^4-2a^3\implies p\mid a-2$ and $p\mid b-2$, impossible. Therefore 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.
vsamc
3789 posts
#20
Y by
EDIT: Oops, Bezout is a thing with $>2$ elements? I just applied it $3$ times to sets of two elements :wallbash:
Solution
This post has been edited 1 time. Last edited by vsamc, Jun 9, 2023, 6:43 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AtharvNaphade
341 posts
#21
Y by
Is this a fakesolve? Seems too straightforward for a 25 MOHS.
At least one of $a, b$ is odd, and since $c = b^2 - a$ is also in the set and $\gcd(b^2 - a, a) = 1$. Other elements in the set are clearly $d = (c^2 - a)^2$ and $e = (c^2 - c)^2.$ Then note that $$\gcd(c+a, (c^2 - a)^2-(c^2 - c)^2) =\gcd(c+a, (a^2-a)^2 - (a^2+a)^2) = \gcd(b^2, 4a^3) = 1.$$Similarly $$\gcd(c-a, (c^2 - a)^2-(c^2 - c)^2) = 1,$$so $\gcd(c^2 - a^2, d^2-e^2) = 1$.
Call $v = c^2 - b^2, w = d^2 - e^2$.
Now note that $$x\in S \implies c^2 - (b^2 - x) = x + v \in S, \text{similarly  } x - v \in S,$$similarly $x \in S \implies x + w \in S, x -w \in S$. Now since $\gcd(v, w) = 1$, by bezout's all integers are then in $S$.
This post has been edited 1 time. Last edited by AtharvNaphade, Sep 12, 2023, 9:59 PM
Reason: e
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1540 posts
#22
Y by
Note that if $x, m, n \in S$ then it follows that $m^2 - (n^2 - x) = x + (m^2 - n^2) \in S$.

Claim: $S$ contains every residue $\pmod{p^k}$ for prime power $p^k$.
Proof. Note that if we show this for $k = 1$, it follows for all $k$. FTSOC suppose not. It must follow that $m^2 \equiv n^2$ for any $m, n \in S$, so $S$ can only take on residue $\pm a$.
WLOG guarentee that $a$ appears. However, it then follows that $a^2 - a \equiv \pm a$, so either $a \equiv 0$ or $a \equiv 2$.
If all residues are $0 \pmod{p}$ or $p = 2$, then this contradicts relatively prime $a, b$. If all residues are $2 \pmod{p}$, then this contradicts relatively prime $a - 2, b - 2$.
Else, $2^2 - 0 = 4$ is nonzero $\pmod{p}$. $\blacksquare$
As such, it follows that $S$ reaches every residue $\pmod{a^2 - b^2}$. Shifting by $a^2 - b^2$ repeatedly gives the result.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8860 posts
#23
Y by
The first observation is counterintuitively very tricky to get.

The key observation is that if $x, a, b$ are elements of $S$, then $x + a^2 - b^2 \in S$. Indeed, this follows as $$x+a^2-b^2 = a^2-(b^2-x).$$
Now, let $a, b$ be two elements of $S$ that satisfy (a).

Claim. $\gcd(a^2-b^2, a^2-(b^2-a)^2, b^2-(a^2-b)^2) = 1$.

Proof. Notice that $$\gcd(a^2-b^2, a^2-(b^2-a)^2) = \gcd(2a-b^2, (a-b)(a+b)) = \gcd(2a-b^2, a+b)$$as $$\gcd(2a-b^2, a-b = \gcd(b(b-2), a-b) = 1$$by the conditions in (a). Furthermore, $$\gcd(a^2-(b^2-a)^2, b^2-(a^2-b)^2) = \gcd(2a-b^2, 2b-a^2) = \gcd(a+b+2, 2a-b^2).$$Assume for the sake of contradiction that $d>1$ is the common GCD; then it follows $d \mid a+b$ and $d \mid a+b+2$, so $d=2$. On the other hand, all three terms cannot be even, so this implies $d=1$. $\blacksquare$

Hence by Bezout there exists some combination of $a^2-b^2, a^2-(b^2-a)^2, b^2-(a^2-b)^2$ that sum to $1$ and $-1$. It follows that if $x \in S$, then $x+1$ and $x-1$ are both in $S$, which is enough.
This post has been edited 1 time. Last edited by HamstPan38825, Dec 18, 2023, 4:18 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
795 posts
#24
Y by
Consider the set of integers $T$ such that, for all $t \in T$, $S = S+t$. Notice that showing $1 \in T$ would finish.
  • Suppose $m,n,x \in S$. Then we have $m^2-(n^2-x) = m^2-n^2+x \in S$, so $m^2-n^2 \in T$.
  • Setting $(m,n) = (a,b),(a^2-b,b),(b^2-a,a)$, we find $a^2-b^2,a^2(a^2-2b),b^2(b^2-2a) \in T$.

If $a=b$, they must equal 1, so $1 \in T$. Otherwise, we claim either $\gcd(a^2-b^2,a^2(a^2-2b))$ or $\gcd(a^2-b^2,b^2(b^2-2a))$ equals 1. Note the first expression equals
\[\gcd(a^2-b^2,a^2-2b) = \gcd((a+b)(a-b), b(b-2)) = \gcd((a+b)(a-b),b-2),\]
and since $\gcd(a-b,b-2)=\gcd(a-2,b-2)=1$, the expression equals $\gcd(a+b,b-2)$. Similarily, the second expression equals $\gcd(a+b,a-2)$, so if neither expression equals 1, $\gcd(a-2,b-2)>1$, contradiction.

Since any linear combination of elements in $T$ is also in $T$, Bezout's on the determined coprime pair tells us $1 \in T$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ilikeminecraft
619 posts
#25
Y by
Let an integer $x$ be called translater if $S = S + x.$ I claim there exists a translater:

First, notice that if $x, m, n\in S,$ we have that $n^2 - x\in S,$ and thus, $m^2 - (n^2 - x) = x + m^2 - n^2 \in S,$ and thus, $S = S + m^2 - n ^2.$

Now I claim that $1$ is a translater.

AFTSOC it isn't. Then, because of GCD reasons, we know that the set of alternater integers is all integer multiples of $d$ for some $d > 2.$ We have that the set $S = \{x : x^2\equiv m\pmod d\}.$ Hence, $a^2 \equiv b^2 \equiv (a^2 - a)^2 \equiv (b^2 - b)^2\pmod d.$ Let $p\mid d.$ We now have the following:
\begin{enumerate}
\item $a^2 \equiv (a^2 - a)^2 \implies a^3(a - 2) \equiv 0 \implies a \equiv 0, 2.$
\item similarly, $b\equiv0, 2$
\item $a^2\equiv b^2\pmod p \implies a \equiv \pm b \pmod p \implies a \equiv b \equiv 0$ or $a\equiv b\equiv 2 \pmod p.$ However, in either cases, this is a contradiction.
\end{enumerate}

Hence, 1 is a translater, and so $S = 1 + S,$ which only satisfies for the set $S = \mathbb Z.$
Z K Y
N Quick Reply
G
H
=
a