We have your learning goals covered with Spring and Summer courses available. Enroll today!

G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/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
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
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
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
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, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
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
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
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
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
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
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
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

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
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
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
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
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
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
Friday, Apr 11 - Jun 27
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
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
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

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

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
H not needed
dchenmathcounts   44
N 17 minutes ago by Ilikeminecraft
Source: USEMO 2019/1
Let $ABCD$ be a cyclic quadrilateral. A circle centered at $O$ passes through $B$ and $D$ and meets lines $BA$ and $BC$ again at points $E$ and $F$ (distinct from $A,B,C$). Let $H$ denote the orthocenter of triangle $DEF.$ Prove that if lines $AC,$ $DO,$ $EF$ are concurrent, then triangle $ABC$ and $EHF$ are similar.

Robin Son
44 replies
dchenmathcounts
May 23, 2020
Ilikeminecraft
17 minutes ago
IZHO 2017 Functional equations
user01   51
N 38 minutes ago by lksb
Source: IZHO 2017 Day 1 Problem 2
Find all functions $f:R \rightarrow R$ such that $$(x+y^2)f(yf(x))=xyf(y^2+f(x))$$, where $x,y \in \mathbb{R}$
51 replies
user01
Jan 14, 2017
lksb
38 minutes ago
chat gpt
fuv870   2
N 39 minutes ago by fuv870
The chat gpt alreadly knows how to solve the problem of IMO USAMO and AMC?
2 replies
fuv870
an hour ago
fuv870
39 minutes ago
Inequality with wx + xy + yz + zw = 1
Fermat -Euler   23
N 41 minutes ago by hgomamogh
Source: IMO ShortList 1990, Problem 24 (THA 2)
Let $ w, x, y, z$ are non-negative reals such that $ wx + xy + yz + zw = 1$.
Show that $ \frac {w^3}{x + y + z} + \frac {x^3}{w + y + z} + \frac {y^3}{w + x + z} + \frac {z^3}{w + x + y}\geq \frac {1}{3}$.
23 replies
Fermat -Euler
Nov 2, 2005
hgomamogh
41 minutes ago
No more topics!
Number theory - Iran
soroush.MG   30
N Yesterday at 10:07 PM by alexanderhamilton124
Source: Iran MO 2017 - 2nd Round - P1
a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$

b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$
30 replies
soroush.MG
Apr 20, 2017
alexanderhamilton124
Yesterday at 10:07 PM
Number theory - Iran
G H J
G H BBookmark kLocked kLocked NReply
Source: Iran MO 2017 - 2nd Round - P1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
soroush.MG
158 posts
#1 • 2 Y
Y by HWenslawski, Adventure10
a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$

b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$
This post has been edited 3 times. Last edited by soroush.MG, Apr 20, 2017, 10:08 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
RagvaloD
4871 posts
#2 • 3 Y
Y by ffff6023, Adventure10, Mango247
a) $gcd(a_{2i}+2j,a_{2j}+2i)=1 \to a_{2i}$ or $a_{2j}$ is odd. Let it is $a_{2i}$
$gcd(a_{2i}+(2j+1),a_{2j+1}+2i)=1 \to a_{2j+1}$ is odd for every $j$
$2|gcd(a_{2i+1}+(2j+1),a_{2j+1}+(2i+1)) $ - contradiction
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
nmd27082001
486 posts
#3 • 3 Y
Y by AHKR, Hasin_Ahmad, Adventure10
my idea:($a_i+j,a_j+i$)=($a_i+i+a_j+j,a_i+j$)
then we take $a_i+i$=1(mod p) then $a_i+i+a_j+j$=2(mod p) with all odd prime p
so we complete
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
soroush.MG
158 posts
#4 • 3 Y
Y by Wizard_32, Adventure10, Mango247
For b I let:
$a_1=p , a_2=p-1 , a_3=p-2 , ... , a_p=1$
$a_{p+1}=p , a_{p+2}=p-1 , a_{p+3}=p-2 , ... , a_{2p}=1$
$a_{2p+1}=p , a_{2p+2}=p-1 , a_{2p+3}=p-2 , ... , a_{3p}=1$
$...$
And proof is easy...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MahyarSefidgaran
5 posts
#5 • 1 Y
Y by Adventure10
Another Problem:
Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$
What if the sequence is a permutation of $\mathbb{N}$ ?
This post has been edited 2 times. Last edited by MahyarSefidgaran, Apr 22, 2017, 9:14 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ABCDE
1963 posts
#6 • 3 Y
Y by SarveshSurya77, Adventure10, Mango247
https://artofproblemsolving.com/community/c6h1268919p6622862
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
oneCUBAN
136 posts
#7 • 4 Y
Y by Mathematicsislovely, SarveshSurya77, Adventure10, Mango247
MahyarSefidgaran wrote:
Another Problem:
Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$
What if the sequence is a permutation of $\mathbb{N}$ ?

IMO Shorlist 2015, N7, about good functions
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Math-Ninja
3749 posts
#8 • 3 Y
Y by SarveshSurya77, Adventure10, Mango247
oneCUBAN wrote:
MahyarSefidgaran wrote:
Another Problem:
Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$
What if the sequence is a permutation of $\mathbb{N}$ ?

IMO Shorlist 2015, N7, about good functions

useless bump
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
oneCUBAN
136 posts
#9 • 2 Y
Y by Adventure10, Mango247
Math-Ninja wrote:
oneCUBAN wrote:
MahyarSefidgaran wrote:
Another Problem:
Do there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)\leq2$
What if the sequence is a permutation of $\mathbb{N}$ ?

IMO Shorlist 2015, N7, about good functions

useless bump

No, the sequence exist in most general way, with $i\neq j$. The other part is your
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
A-Thought-Of-God
454 posts
#10 • 2 Y
Y by amar_04, ClassyPeach
Storage.
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
heheXD1
429 posts
#12 • 1 Y
Y by ClassyPeach
Proof for Part 1

Construction for Part 2
This post has been edited 1 time. Last edited by heheXD1, Jan 3, 2021, 9:16 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
508669
1040 posts
#13 • 1 Y
Y by A-Thought-Of-God
soroush.MG wrote:
a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$

b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$

a) For this part, let us assume for the sake of contradiction that there does exists such a sequence $a_1, a_2, a_3 \dots \in \mathbb{N}$. Choose $i = 2m, j = 2n$ where $m \neq n$. We get that $\text{gcd}(a_{2m} + 2n, a_{2n} + 2m) = 1$ which is impossible if both $a_{2m}, a_{2n}$ are even and so one of $a_{2m}, a_{2n}$ is odd, let us say without loss of generality that $a_{2m}$ is odd. Then choose $i = 2m, j = 2r+1$ and we see that $\text{gcd}(a_{2m} + 2r + 1, a_{2r+1} + 2m) = 1$ which means that necessarily $a_{2r+1}$ is always odd, now choose $i = 2r_1 + 1, j = 2r_2 + 1$ and see that $\text{gcd}(a_{2r_1+1} + 2r_2 + 1, a_{2r_2+1}+2r_1+1) \geq 2 = 1$ which is a contradiction and hence our assumption is wrong as desired.

b) For this part, since $p$ is an odd prime, take $a_i \in \mathbb{Z}_p$ such that $a_1 \equiv 1 - i \pmod{p}$. We see that $a_i + j \equiv a_j + i \equiv 0 \pmod{p} \implies 1 - i + j \equiv 1 - j + i \equiv 0 \pmod{p} \implies i - j \equiv j - i \equiv 1 \pmod{p} \implies (i-j) + (j-i) = 0 \equiv 2 \pmod{p}$ which is a contradiction, implying that $a_i + j, a_j + i \not\equiv 0 \pmod{p}$ for all $(i, j) \in \mathbb{N}$ which is the desired contradiction.
This post has been edited 1 time. Last edited by 508669, Feb 25, 2021, 8:47 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maths_1729
390 posts
#14
Y by
soroush.MG wrote:
a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$

b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$

FTSOC assume there exist such sequence in $N$.
Case 1-: if $a_1$ is odd then as we need $gcd(a_1+3,a_3+1)=1$ So $a_3$ must be even.
Now as $gcd(a_2+3, a_3+2)=1$ then $a_2$ must be odd. Now we need $a_4$ such that $gcd(a_3+4, a_4+3)=gcd(a_2+4, a_4+2)=1$ but observe if $a_4$ is even then $gcd(a_3+4, a_4+3)\neq 1$ and similarly if $a_4$ is odd then $gcd(a_2+4, a_4+2)\neq 1$. Hence contradiction.

Case 2-: if $a_1$ is even then $gcd(a_1+2,a_{2}+1)=1$ so $a_{2}$ is even and $gcd(a_2+4,a_4+2)=1$ so $a_4$ is odd. But then $gcd(a_1+4,a_4+1)\neq 1$ Hence contradiction.
So No such sequence exist.
soroush.MG wrote:
b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$

For any odd prime $p$ we can always have a sequence $a_i\equiv 1-i\mod p$ which indeed satisfy $p\nmid gcd(a_i+j,a_j+i)=1$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathForesterCycle1
79 posts
#16
Y by
dame dame
This post has been edited 2 times. Last edited by MathForesterCycle1, Oct 17, 2021, 5:22 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Project_Donkey_into_M4
136 posts
#17
Y by
solution

I was most ridiculous in forcing the $a_i$'s I hope my sequence works :)
This post has been edited 2 times. Last edited by Project_Donkey_into_M4, Nov 24, 2021, 8:24 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Williamgolly
3760 posts
#18 • 1 Y
Y by sabkx
Oops fakesolved part b

Part a)

Suppose \( (i,j) = (2m, 2t+1) \) where $m$ is fixed and $t$ varies We have

\[ \text{gcd}(a_{2m}+(2t+1), a_{2t+1}+(2m) ) = 1\]
which implies \( (a_{2m}, a_{2t+1}) = (0,0), (1,1) \) where we take \( a_{2m}, a_{2t+1} \in \mathbb{Z}_2 \)

Thus, our ordered triple becomes either

\[ (a_1, a_2, a_3, a_4,  ... ) = (0,0,0,0, ... ) \]
or

\[ (a_1,a_2,a_3,a_4, ... ) = (1,1,1,1, ... ) \]
Case 1: \( (a_1, a_2, a_3, a_4,  ... ) = (0,0,0,0, ... ) \)
Take \( (i,j) = (2,4) \) and we have \( \text{gcd}(a_2+4, a_4+2) = 2 \), contradiction.

Case 2: \( (a_1,a_2,a_3,a_4, ... ) = (1,1,1,1, ... ) \)
Take \( (i,j) = (1,3) \) and we have \( \text{gcd}(a_1+3, a_3+1) = 2 \), contradiction.

Thus, no sequence of $a_{i, i \geq 1}$ exists.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jelena_ivanchic
151 posts
#19 • 4 Y
Y by Periwinkle27, proxima1681, Pranav1056, Jupiter_is_BIG
Solved with Periwinkle27 and Proxima1681.
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mogmog8
1080 posts
#20 • 1 Y
Y by centslordm
(a) Assume the contrary. Notice if $2\nmid a_{2n}$ for any $n,$ then $\gcd(a_{2m+1}+2n,a_{2n}+2m+1)=1$ or $2\mid a_{2m+1}$ for all $m.$ Then, $$\gcd(a_{2m+1}+2k+1,a_{2k+1}+2m+1)\ge 2,$$a contradiction. Hence, we assume $2\mid a_{2n}$ for all $n,$ which implies $$\gcd(a_{2n}+2k,a_{2k}+2n)\ge 2,$$a contradiction.

(b) Let $a_i\equiv 1-i\pmod{p},$ and assume FTSOC that $$p\mid\gcd(a_i+j,a_j+i)\implies p\mid a_i+j\land p\mid a_j+i.$$Then, $1-i+j\equiv 1-j+i\equiv 0\pmod{p},$ or $-1\equiv 1\pmod{p}\implies p\mid 2.$ $\square$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
minusonetwelth
225 posts
#21
Y by
a) We first observe that there can be at most one even integer $a_m$ with an even index $m$, as otherwise, if there is another integer with an even index, say $a_n$, then $\gcd(a_n+m,a_m+n)=2$. Similarly, there can be at most one odd number $a_r$ with an odd index $r$. Hence, for all the other numbers, the paritity of $a_i$ and $i$ are different. Among those, choose an even $i$ and any odd $j>i$. This also immediatily implies that $\gcd(a_i+j,a_j+i)=2$.
b) We claim that $a_i=1-i\mod p$ works for any odd prime $p$. First note if $p$ does not divide $a_j+i+a_i+j$, then $p$ can't divide both of $a_i+j$ and $a_j+i$, and hence cannot divide their gcd. Now,
$$a_j+i+a_i+j=1-i+i+1-j+j=2\mod p$$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.
dwip_neel
40 posts
#22
Y by
(a) For the sake of contradiction, we assume the given condition to be false. Consider $a_1$ is odd.

\[\gcd(a_1 + 2k + 1, a_{2k + 1} + 1) = 1\]So, $\forall k \in \mathbb{N}, a_{2k + 1} + 1$ is odd. Consider $a_2$ is odd. Then,
\[\gcd(a_2 + 3, a_3 + 2) = 1\]$a_2$ is assumed odd, $a_3 + 2 \in \text{even}$. Hence, $2 \mid a_2 + 3$ and $2 \mid a_3 + 2$. Contradiction. So, $a_2$ is even.
\[\gcd(a_2 + 4, a_4 + 2) = 1\]$2 \mid a_2 + 4$, so $a_4 + 2$ is odd $\implies a_4$ is odd.
\[\gcd(a_4 + 5, a_5 + 4) = 1\]$a_5$ is even and so does $a_5 + 4$. Check that, $2 \mid a_4 + 5$, contradiction! Now, we assumed $a_1$ to be odd. Now, we are left with the part $a_1$ to be even.
\[\gcd(a_1 + 2k, a_{2k} + 1) = 1\]$a_{2k} + 1$ must be odd. So, $\forall k \in \mathbb{N}, a_{2k}$ is even. Hence, $a_2$ is even. Let's assume $a_3$ is even too.

\[\gcd(a_3 + 1, a_1 + 3) = 1\]Contradiction. So, $a_3$ is odd.
\[\gcd(a_3 + 2k + 1, a_{2k + 1} + 3) = 1\]Hence, $a_{5}$ is even. Now, note that,
\[d \mid a_1 + 5 \text{ and } d \mid a_5 + 1\]\[d \mid (a_5 - a_1) - 4\]$a_5$ and $a_1$ both are even, hence $d \geq 2$, contradiction! :-D
This post has been edited 1 time. Last edited by dwip_neel, Jan 9, 2023, 11:48 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
s12d34
3359 posts
#23
Y by
1. Assume, with contradiction, that such a sequence exists for the given conditions.

Consider $(i,j)=(2a,2b) \implies \gcd(a_{2a}+2b,a_{2b}+2a)=1.$ Note that for the latter condition to hold, we must have at most $1$ value of $i$ for which $a_{2i}$ is even. Therefore, $a_{2n} \equiv a_{2m} \equiv 1 \pmod{2}.$ From here, we can proceed with casework.

Case 1. $(i,j)=(2n+1,2m) \implies \gcd(a_{2n}+2m,2_{2m}+2n+1)=1.$ However, since $a_{2m}$ is odd, $a_{2m}+2n+1$ is even, and hence $a_{2n+1}+2m$ must be odd, so $a_{2n+1}$ is odd.

Case 2. $(i,j)=(2n,2m+1) \implies \gcd(a_{2n}+2m+1,a_{2m+1}+2n)=1.$ However, since $a_{2n}$ is odd, $a_{2n}+2m+1$ is even, and hence $a_{2m+1}+2n$ must be odd, so $a_{2m+1}$ is odd.

Now, note that considering $(i,j)=(2n+1,2m+1) \implies \gcd(a_{2n+1}+2m+1,a_{2m+1}+2n+1)=1,$ we cannot have both $a_{2n+1}$ and $a_{2m+1}$ be odd, since then there would be more than one value of $i$ for which $a_{2i}$ is even, and hence $\gcd(a_{2n+1}+2m+1,a_{2m+1}+2n+1) \neq 1,$ a contradiction.

2. Note that $a_i=ip+1-i$ holds since $p$ is an odd prime.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
miguel00
576 posts
#25
Y by
1. Assume there exists a sequence that satisfies the conditions. Observe when $i,j = 2m,2n$ and $i,j = 2m+1,2n+1$. Then, $gcd(a_{2m} + 2n, a_{2n} + 2m) = 1$, so this means that at least one of $2m$ and $2n$ is odd. $gcd(a_{2m+1} + 2n+1, a_{2n+1} + 2m+1) = 1$ and this means that at least one of $2m+1$ and $2n+1$ is odd. Now, by comparing $i,j$ that is odd and even, we arrive at a contradiction as gcd has to be 2.

2. Note that $a_i = p(1-i)+pk$ works where is a variable that makes $a_i$ positive.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
David_Kim_0202
383 posts
#26
Y by
soroush.MG wrote:
a) Prove that there doesn't exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: gcd(a_i+j,a_j+i)=1$

b) Let $p$ be an odd prime number. Prove that there exist sequence $a_1,a_2,a_3,... \in \mathbb{N}$ such that: $\forall i<j: p \not | gcd(a_i+j,a_j+i)$

a. If we place $a_1$ as an odd number we will get a contradiction because we could pair all fo $a_n$ and we will see that all of $a_(odd)$ will be odd so we could not pair two odd $a_i$ because we will get an $gcd$ of a multiple of 2. Therefore, $a_1$ is even, and also because of the previous temp, we get all even terms odd and every odd ters even and we will get a contradiction if we pair 1 even term and 1 odd term.

b. just make the ters of mod 3 like 2, 1, 0 then it will work
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lian_the_noob12
173 posts
#28
Y by
jelena_ivanchic wrote:
Solved with Periwinkle27 and Proxima1681.
solution

No, Your construction for part b doesn't work. As,
$gcd(a_{p-1} + p, a_p + p-1)=gcd(p(i+1),p)=p$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cursed_tangent1434
548 posts
#29
Y by
Solved with kingu. I'm not entirely sure what possessed me when I didn't notice parity arguments killed part (a), of course our god kept his calm and carried as usual.

(a) Say there exists such a sequence. We consider two even indices $i$ and $j$. Then, $a_i +i$ and $a_j+j$ can't both be even, so one of $a_i$ and $a_j$ is clearly odd. Say it is $a_i$. Then, for all odd integers $k$ , $a_i+k$ is even. Thus, $a_k+i$ cannot be even, which implies that $a_k$ is odd for all odd integers $k$. But then, considering two odd integers $k_1$ and $k_2$ we have that $a_{k_1}+k_2 $ and $a_{k_2}+k_1$ are both even, and thus there $\text{gcd}$ is greater than 1. Contradiction! Thus, there cannot exist such a sequence.

(b) Consider the sequence $a_{pk}=pk-(p-1), a_{pk-1}=pk-(p-2) , \dots a_{pk-(p-1)}=pk$ for all positive integers $k$. In particular, here $a_i \equiv (p+1) -i \pmod{p}$ for all indices $i$. Then, say there exists two indices $i$ and $j$ which violate the desired condition. Then, $a_i+j \equiv (p+1)-i+j$ and $a_j+i \equiv (p+1)-j+i$. But, if
\[p \mid (p+1)-i+j \implies p \mid j-i +1 \text{ and } p \mid (p+1)-j+i \implies p\mid i-j+1\]summing implies that $p \mid (i-j+1)+(j-i+1) = 2$ which is a clear contradiction. Thus, this sequence indeed satisfies the given condition and we are done. (This actually solves the extension in #5 as well).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
KevinYang2.71
392 posts
#30 • 1 Y
Y by deduck
a) Assume FTSOC such a sequence exists. Since $\gcd(a_2+4,a_4+2)=1$, it follows that $a_2$ or $a_4$ is odd. WLOG $a_2$ is odd. Then $\gcd(a_2+n,a_n+2)=1$ so $a_n$ is odd if $n$ is odd. But $a_1+3$ and $a_3+1$ are both even, a contradiction. $\square$

b) Choose $a_i$ such that $a_i+i\equiv1\pmod{p}$. Then $\gcd(a_i+j,a_j+i)=\gcd(a_i+i+a_j+j,a_j+i)$ is not divisible by $p$ since $a_i+i+a_j+j\equiv 2\pmod{p}$. $\square$
This post has been edited 1 time. Last edited by KevinYang2.71, Jun 28, 2024, 10:33 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Saucepan_man02
1294 posts
#31 • 1 Y
Y by MihaiT
a) Consider $(2m, 2n)$: $(a_{2m}+2n, a_{2n}+2m) = 1$ implies that either $a_{2n}$ or $a_{2m}$ is odd. WLOG let $a_{2n}$ to be odd. Then: $$(a_{2n}+2k+1, a_{2k+1}+2n) = 1$$implies $a_{2k+1}$ is odd for all integers $k \ge 0$. Notice that: $$(a_{2k+1}+2t+1, a_{2t+1}+2k+1)=1$$implies $a_{2t+1}$ to be even, contradiction. There doesnt exists such a sequence.

b) The sequence $a_i = pi+1-i$ evidently works and we are done.
(For intuition on getting the sequence $a_i$)
Notice that: $p \nmid \gcd(a_i+j,a_j+i) = \gcd(a_i+j + a_j + i,  a_i,a_j+i)$ thus: $p \nmid a_i+a_j + i + j$. Taking any sequence $a_i$ which satisfies these conditions would work 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.
MihaiT
741 posts
#32
Y by
Saucepan_man02 wrote:
a) Consider $(2m, 2n)$: $(a_{2m}+2n, a_{2n}+2m) = 1$ implies that either $a_{2n}$ or $a_{2m}$ is odd. WLOG let $a_{2n}$ to be odd. Then: $$(a_{2n}+2k+1, a_{2k+1}+2n) = 1$$implies $a_{2k+1}$ is odd for all integers $k \ge 0$. Notice that: $$(a_{2k+1}+2t+1, a_{2t+1}+2k+1)=1$$implies $a_{2t+1}$ to be even, contradiction. There doesnt exists such a sequence.

b) The sequence $a_i = pi+1-i$ evidently works and we are done.
(For intuition on getting the sequence $a_i$)
Notice that: $p \nmid \gcd(a_i+j,a_j+i) = \gcd(a_i+j + a_j + i,  a_i,a_j+i)$ thus: $p \nmid a_i+a_j + i + j$. Taking any sequence $a_i$ which satisfies these conditions would work and we are done.

new and nice solution!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Autistic_Turk
9 posts
#33
Y by
just put
a_i= p-1 if i is divisible by p
a_i=p if i isnt divisible by p and a_i reminder by p isnt 1
a_i=1 if else
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MR.1
91 posts
#35
Y by
First one is just $\pmod{2}$
And my "ahh construction" for second problem :noo:
$a_i=(p-1)!^{2i}-i$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
alexanderhamilton124
375 posts
#36
Y by
Ezpz

Consider $a_i$ for some odd $i$. If $a_i$ is even, take $j$ even (any even), which gives that $a_j$ must be even. Note $\gcd(a_2 + 4, a_4 + 2) = 1$ a contradiction since $2 \mid a_2, 2 \mid a_4$. If $a_i$ is odd, consider any other odd, $j$. This gives $a_j + i$ odd which means $a_j$ even, and we finish like earlier.

For the second part, take $a_x \equiv 1 - x \mod{p}$, which finishes.
Z K Y
N Quick Reply
G
H
=
a