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
Find all functions $f$ is strictly increasing : \(\mathbb{R^+}\) \(\rightarrow\)
guramuta   3
N 18 minutes ago by ja.
Find all functions $f$ is strictly increasing : \(\mathbb{R^+}\) \(\rightarrow\) \(\mathbb{R^+}\) such that:
i) $f(2x)$ \(\geq\) $2f(x)$
ii) $f(f(x)f(y)+x) = f(xf(y)) + f(x) $
3 replies
guramuta
Yesterday at 1:45 PM
ja.
18 minutes ago
Fourth powers and square roots
willwin4sure   39
N 24 minutes ago by awesomeming327.
Source: USA TSTST 2020 Problem 4, by Yang Liu
Find all pairs of positive integers $(a,b)$ satisfying the following conditions:
[list]
[*] $a$ divides $b^4+1$,
[*] $b$ divides $a^4+1$,
[*] $\lfloor\sqrt{a}\rfloor=\lfloor \sqrt{b}\rfloor$.
[/list]

Yang Liu
39 replies
willwin4sure
Dec 14, 2020
awesomeming327.
24 minutes ago
Interesting inequalities
sqing   1
N 27 minutes ago by sqing
Source: Own
Let $ a,b >0 $ and $ a^2-ab+b^2\leq 1 $ . Prove that
$$a^4 +b^4+\frac{a }{b +1}+ \frac{b }{a +1} \leq 3$$$$a^3 +b^3+\frac{a^2}{b^2+1}+ \frac{b^2}{a^2+1} \leq 3$$$$a^4 +b^4-\frac{a}{b+1}-\frac{b}{a+1} \leq 1$$$$a^4+b^4 -\frac{a^2}{b^2+1}- \frac{b^2}{a^2+1}\leq 1$$$$a^3+b^3 -\frac{a^3}{b^3+1}- \frac{b^3}{a^3+1}\leq 1$$
1 reply
1 viewing
sqing
30 minutes ago
sqing
27 minutes ago
Sum of 1/(a^5(b+2c))^2 at least 1/3 [USA TST 2010 2]
MellowMelon   42
N 33 minutes ago by Adywastaken
Let $a, b, c$ be positive reals such that $abc=1$. Show that \[\frac{1}{a^5(b+2c)^2} + \frac{1}{b^5(c+2a)^2} + \frac{1}{c^5(a+2b)^2} \ge \frac{1}{3}.\]
42 replies
MellowMelon
Jul 26, 2010
Adywastaken
33 minutes ago
Weird function?
ItzsleepyXD   2
N an hour ago by ItzsleepyXD
Source: Own
Find all functions \( f: \mathbb{R} \rightarrow \mathbb{R} \) such that for all \( x, y \in \mathbb{R} \),
\[
f(x + f(2y)) + f(x^2 - y) = f(f(x)) f(x + 1) + 2y - f(y).
\]
2 replies
ItzsleepyXD
Apr 11, 2025
ItzsleepyXD
an hour ago
Almost similar one but more answer lol
ItzsleepyXD   0
an hour ago
Source: Own , Modified
Find all non decreasing functions or non increasing function $f \colon \mathbb{R} \to \mathbb{R}$ such that for all $x,y \in \mathbb{R}$

$$ f(x+f(y))=f(x)+f(y) \text{ or } f(f(f(x)))+y$$.
0 replies
ItzsleepyXD
an hour ago
0 replies
A lot of unexpected answer from non decreasing function
ItzsleepyXD   0
an hour ago
Source: Own
Find all non decreasing function $f : \mathbb{R} \to \mathbb{R}$ such that for all $x,y \in  \mathbb{R}$ and $m,n \in \mathbb{N}_0$ such that $m+n \neq 0$ there exist $m',n' \in \mathbb{N}_0$ such that $m'+n'=m+n+1$ and $$f(f^m(x)+f^n(y))=f^{m'}(x)+f^{n'}(y)$$. Note : $f^0(x)=x$ and $f^{n}(x)=f(f^{n-1}(x))$ for all $n \in \mathbb{N}$ . original
0 replies
ItzsleepyXD
an hour ago
0 replies
Cute Inequality
EthanWYX2009   0
2 hours ago
Let $a_1,\ldots ,a_n\in\mathbb R\backslash\{0\},$ determine the minimum and maximum value of
\[\frac{\sum_{i,j=1}^n|a_i+a_j|}{\sum_{i=1}^n|a_i|}.\]
0 replies
EthanWYX2009
2 hours ago
0 replies
Interesting inequality
sealight2107   3
N 2 hours ago by NguyenVanHoa29
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}$
3 replies
sealight2107
May 6, 2025
NguyenVanHoa29
2 hours ago
Is this FE is solvable?
ItzsleepyXD   0
2 hours ago
Source: Own , If not appear somewhere before
Find all function $f : \mathbb{R} \to \mathbb{R}$ such that for all $x,y \in  \mathbb{R}$ . $$f(x+f(y))+f(x+y)=2x+f(y)+f(f(y))$$. Original
0 replies
ItzsleepyXD
2 hours ago
0 replies
Symmetry in Circumcircle Intersection
Mimii08   2
N 2 hours ago by mashumaro
Hi! Here's another geometry problem I'm thinking about, and I would appreciate any help with a proof. Thanks in advance!

Let AD and BE be the altitudes of an acute triangle ABC, with D on BC and E on AC. The line DE intersects the circumcircle of triangle ABC again at two points M and N. Prove that CM = CN.

Thanks for your time and help!
2 replies
Mimii08
4 hours ago
mashumaro
2 hours ago
Blue chessboard
rcorreaa   10
N 2 hours ago by Jaxman8
Source: 2022 Brazilian National Mathematical Olympiad - Problem 6
Some cells of a $10 \times 10$ are colored blue. A set of six cells is called gremista when the cells are the intersection of three rows and two columns, or two rows and three columns, and are painted blue. Determine the greatest value of $n$ for which it is possible to color $n$ chessboard cells blue such that there is not a gremista set.
10 replies
rcorreaa
Nov 22, 2022
Jaxman8
2 hours ago
Substitution
JCE   3
N 2 hours ago by K124659
I've been working on this for about an hour or so, and I can't get this problem. I know the answer, but no idea on how to find it.
Please help?

2x-y^2=4
x^2+y=14
3 replies
JCE
May 27, 2006
K124659
2 hours ago
Something nice
KhuongTrang   34
N 3 hours ago by TNKT
Source: own
Problem. Given $a,b,c$ be non-negative real numbers such that $ab+bc+ca=1.$ Prove that

$$\sqrt{a+1}+\sqrt{b+1}+\sqrt{c+1}\le 1+2\sqrt{a+b+c+abc}.$$
34 replies
KhuongTrang
Nov 1, 2023
TNKT
3 hours ago
Number theory
falantrng   38
N Apr 25, 2025 by Ilikeminecraft
Source: RMM 2018 D2 P4
Let $a,b,c,d$ be positive integers such that $ad \neq bc$ and $gcd(a,b,c,d)=1$. Let $S$ be the set of values attained by $\gcd(an+b,cn+d)$ as $n$ runs through the positive integers. Show that $S$ is the set of all positive divisors of some positive integer.
38 replies
falantrng
Feb 25, 2018
Ilikeminecraft
Apr 25, 2025
Number theory
G H J
G H BBookmark kLocked kLocked NReply
Source: RMM 2018 D2 P4
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
falantrng
252 posts
#1 • 8 Y
Y by Davi-8191, Mathuzb, anantmudgal09, Amir Hossein, otsin, HWenslawski, megarnie, Adventure10
Let $a,b,c,d$ be positive integers such that $ad \neq bc$ and $gcd(a,b,c,d)=1$. Let $S$ be the set of values attained by $\gcd(an+b,cn+d)$ as $n$ runs through the positive integers. Show that $S$ is the set of all positive divisors of some positive integer.
This post has been edited 2 times. Last edited by v_Enhance, Feb 25, 2018, 11:06 AM
Reason: LaTeX copy edits
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
#2 • 11 Y
Y by xdiegolazarox, rkm0959, McTeague, Amir Hossein, yushanlzp, v4913, HWenslawski, HamstPan38825, Adventure10, iamnotgentle, Jupiterballs
First note that elements of $S$ a all must divide $c(an+b)-a(cn+d) = bc - ad \neq 0$.

Next, we show $S$ is closed downwards.

Claim: Suppose $k \in S$ and the prime $p$ divides $k$. Then $k/p \in S$ as well. Consequently, all divisors of $k$ are in $S$.

Proof. Let $p \mid k = \gcd(an+b,cn+d)$; it follows $p \nmid \gcd(a,c)$ (since otherwise $p \mid \gcd(a,b,c,d)$ too). So WLOG $a \not\equiv 0 \pmod p$.

Let $e = \nu_p(k)$ and construct $n'$ (by Chinese theorem) such that \begin{align*} 		n' &\equiv n + p^{e-1} \pmod{p^e} \\ 		\text{and} \quad n' &\equiv n \pmod{q} 	\end{align*}for any prime power $q$ dividing $bc-ad$. We contend $\gcd(an'+b, cn'+d) = k/p$.

Indeed $\nu_p(an'+b) = e-1$ and $\nu_p(cn'+d) \ge e-1$. So the exponent of $p$ in $\gcd(an'+b,cn'+d)$ is correct. Moreover, since $n' \equiv n \pmod{q}$, the exponents of any other primes do not change. $\blacksquare$

Next, we prove $S$ is closed under LCM's.

Claim: Suppose $k_1, k_2 \in S$. Then $\operatorname{lcm}(k_1, k_2) \in S$.

Proof. By the previous claim it suffices to show some multiple of $\operatorname{lcm}(k_1, k_2)$ is in $S$. If $k_1 = \gcd(an_1+b, cn_1+d)$ and $k_2 = \gcd(an_2+b, cn_2+d)$.

We choose $n$ such that: for each prime $p \mid ad-bc$, if $q = p^{\nu_p(bc-ad)}$ then \[ 		n \equiv 		\begin{cases} 			n_1 \pmod q & \nu_p(k_1) \ge \nu_p(k_2)\\ 			n_2 \pmod q & \text{otherwise}. 		\end{cases} 	\]Then $\nu_p(\gcd(an+b, cn+d)) \ge \max(\nu_p(k_1), \nu_p(k_2))$ for each $p$ as desired. $\blacksquare$

Thus if $m = \max S < \infty$ then $S$ consists of exactly the divisors of $m$.

Remark: One can also proceed by using the Euclidean algorithm. Indeed, $\gcd(an+b,cn+d) = \gcd( (a-c)n+(b-d), cn+d )$, and if $(a,b,c,d)$ satisfies the problem conditions then so does $(a-c,b-d,c,d)$. By repeating this we find it suffices to consider the case $a=0$, which can be done essentially by hand.
This post has been edited 1 time. Last edited by v_Enhance, Mar 6, 2018, 6:03 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rkm0959
1721 posts
#3 • 3 Y
Y by BobaFett101, richrow12, Adventure10
Probably the best problem of RMM this year imho...

Sketch

Full Write-Up
This post has been edited 5 times. Last edited by rkm0959, Feb 25, 2018, 1:54 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
FabrizioFelen
241 posts
#4 • 2 Y
Y by xdiegolazarox, Adventure10
This problem was proposed by Raul Alcántara, Peru.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
xdiegolazarox
42 posts
#5 • 3 Y
Y by FabrizioFelen, Adventure10, Mango247
rkm0959 wrote:
Does anyone know of a closed form for M?

Nvm RMM official solution kinda gives it away.

A close form of $M$ could be the greater positive divisor of $ab-cd$ which has not common prime divisors with $gcd(a,c)$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
WizardMath
2487 posts
#6 • 2 Y
Y by Adventure10, Mango247
Strangely, it seems to be harder than #5 and #6 (or maybe I am weird)

My solution (along with how it was motivated, just for storage):

It is clear that $S$ is finite, as the mentioned $\gcd$ divides $c(an+b)-a(cn+d) = bc - ad$.

Consider the maximum element of the set $S$. The idea is to decrease the exponent of any prime in the prime factorisation of a number in the set $S$ by exactly one.

Suppose $x$ is in the set, and the corresponding $n$ is $n$. We need to decrease the exponent of a particular prime $p$ dividing $x$ by exactly one, while letting the other primes untouched. So we need to add the prime power just smaller than the one that fully divides $x$. So if we have $\nu_p(x) = v$, then consider the number $m$ such that $m \equiv n + p^{v-1} \pmod{p^v}$ and $m \equiv b \pmod{\frac{bc-ad}{p^{\nu_p(bc-ad)}}}$. This clearly works because $p$ is coprime to the gcd of $a,c$. So atleast one of $am+b, cm+d$ have the highest power of $p$ dividing them as $v-1$, which decreases the power of $p$ in the prime factorisation by exactly one. By performing this procedure for all prime factors of the maximum element of $S$ and repeating it, we are done, after noting that for every pair of elements in $S$, their lcm is in $S$ too ($v_p$ arguments).
This post has been edited 2 times. Last edited by WizardMath, Mar 26, 2018, 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.
cloneofsimo
30 posts
#7 • 2 Y
Y by Adventure10, Mango247
On the test I proved that $S=lcm(ad-bc,b_a,d_c)$, where $x_y = \prod_{v_p(y)<v_p(x), p: prime}^{}  p^{v_p(x)-v_p(y)} gcd(x,y)$. What do you guys think?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
McTeague
55 posts
#8 • 3 Y
Y by v_Enhance, Amir Hossein, Adventure10
@ v_Enhance, WizardMath -- Maybe I'm missing the point of the argument but don't we also need that there is no attainable gcd $x$ such that $x \nmid m$ where $m = \max S$?

If this is an issue, then I think we could finish by proving that if there exist $n_1$ and $n_2$ such that $\gcd(an_1 + b, cn_1 + d) = p^{r+1}q^s x$ and $\gcd(an_2 + b, cn_2 + d) = p^r q^{s+1} x$ with $p$, $q$ primes such that $p, q \nmid x$, then there exists $n$ such that $\gcd(an+b, cn+d) = p^{r+1}q^{s+1}x$, done this way (a bit of an algebraic mess).
This post has been edited 2 times. Last edited by McTeague, Mar 6, 2018, 3:22 PM
Reason: clarification
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 • 4 Y
Y by McTeague, v4913, HamstPan38825, Adventure10
OOPS. You are right. I think you can fix it more simply by just showing the l.c.m. of two elements of $S$ is in $S$ (you do not have to do it at the level of individual primes). I'll edit my post to something hopefully right.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
McTeague
55 posts
#10 • 2 Y
Y by Adventure10, Mango247
Wow! That addition is way more elegant than what I did. Cool!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
R8450932
58 posts
#11 • 1 Y
Y by Adventure10
The following problem was proposed by Iurie Boreico for Mathematical Reflections 2006 Issue 6.
Let $a, b, c, d $ be integers such that $gcd(a, b, c, d) = 1 $ and $ad-bc\neq 0$.
Prove that the greatest possible value of $gcd(ax + by, cx + dy)$ over all pairs
$(x, y)$ of relatively prime is $|ad - bc|.$
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
#12 • 2 Y
Y by Adventure10, Mango247
I think we can potentially clean the write-up (avoiding use of $\operatorname{lcm}(k_1,k_2) \in S$) by taking $M=\prod_{p} p^{k_p}$ where $k_p \le v_p(ad-bc)$ is the maximum exponent of any prime $p$ in the factorisation of elements of $(\gcd(an+b,cn+d))_n$. Now like rkm's solution, we can pick $n$ such that for any $0 \le s_p \le k_p$ $v_p(\gcd(an+b, cn+d)=s_p$ by a simple Hensel's lemma deconstruction on the $n$ that attains maximum $v_p$. Applying CRT for all such primes will produce an $n$ that has the exact $v_p$ sequence as any divisor of $M$ would.
This post has been edited 1 time. Last edited by anantmudgal09, Jun 26, 2018, 10:49 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
#13 • 2 Y
Y by Adventure10, Mango247
v_Enhance wrote:
Remark: One can also proceed by using the Euclidean algorithm.
Basically just writing out this solution fully.

Solution

Remark
This post has been edited 2 times. Last edited by pad, Dec 9, 2019, 2:57 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Stormersyle
2786 posts
#14
Y by
Consider a fixed prime $p$. Let $x=\nu_p(\gcd(an+b, cn+d))$, so we can rewrite $x$ as $x=\min(\nu_p(an+b), \nu_p(cn+d))$. I claim the set of all values $x$ can take is $[0, m]$ for some $m$. To prove this, first note that at least one of $\nu_p(a), \nu_p(b), \nu_p(c), \nu_p(d)$ is $0$. Next, we split the problem into three cases.

Case 1) $\nu_p(a)>\nu_p(b), \nu_p(c)>\nu_p(d)$. Note $\nu_p(an+b)=\nu_p(b), \nu_p(cn+d)=\nu_p(d)$, so $x=\min(\nu_p(b), \nu_p(d))=0$.

Case 2) $\nu_p(a)\le \nu_p(b), \nu_p(c)> \nu_p(d)$. Then, since $\nu_p(cn+d)=\nu_p(d)$, we have $x=\min(\nu_p(an+b), \nu_p(d))$, so $x\le \nu_p(d)$. Now I claim $x$ can take on any integer from $0$ through $\nu_p(d)$. To see this, note that for any $k\ge \nu_p(a)$, we can get $\nu_p(an+b)=k$ by setting $n\equiv (\frac{a}{\nu_p(a)})^{-1} (p^{k-\nu_p(a)}-\frac{b}{\nu_p(a)})\pmod{p^{k+1-\nu_p(a)}}$. Thus, $x$ can take on any value from $\min(\nu_p(a), \nu_p(d))=0$ through $\nu_p(d)$. The $\nu_p(a)>\nu_p(b), \nu_p(c)\le \nu_p(d)$ case is symmetric to this one.

Case 3) $\nu_p(a)\le \nu_p(b), \nu_p(c)\le \nu_p(d)$. First assume $\nu_p(a)=0$; the $\nu_p(c)=0$ case is symmetric. Next, note that $\gcd(an+b, cn+d)|a(cn+d)-c(an+b)=ad-bc$, meaning that $x\le \nu_p(ad-bc)$. Now I claim $x$ can take on any integer from $0$ through $\nu_p(ad-bc)$. To see this, choose any $k\in [0, \nu_p(ad-bc)]$, and set $n\equiv \frac{p^k-b}{a}\pmod{p^{k+1}}$; then, we have $\nu_p(an+b)=k$, so $an+b\equiv 0\pmod{p^k}$, and thus $acn+bc\equiv 0\pmod{p^k}$. But we also have $ad-bc\equiv 0\pmod{p^k}$, so adding gives $acn+ad\equiv 0\pmod{p^k}$, meaning $cn+d\equiv 0\pmod{p^k}$ and thus $\nu_p(cn+d)\ge p^k$, so $x=k$. Hence, $x$ can take any value from $0$ through $\nu_p(ad-bc)$.

Hence, we have proven that for all primes $p$, the set of values $\nu_p(\gcd(an+b, cn+d))$ can take on is any integer in $[0, m_p]$, for integer $m_p$. Additionally, we have also shown that for $k\in [0, m]$, $\nu_p(\gcd(an+b, cn+d))$ takes on $k$ when a particular congruence of the form $n\equiv r\pmod{p^j}$ holds (for instance, in case 3, $j=k+1$ and $r$ is $(p^k-b)a^{-1} \pmod{p^{k+1}}$), so by CRT we are done.

rigorization of the CRT part I guess
This post has been edited 3 times. Last edited by Stormersyle, Mar 23, 2020, 10:03 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
matinyousefi
499 posts
#15 • 1 Y
Y by AlastorMoody
The following problem has appeared in All-Ukrainian MO 2017:

Arithmetic Progressions $\{a_i\},\{b_i\}$ and positive integers $d,m$ are given such that $d \mid m$ assuming there exists indices $i,j,l,k$ satisfying $$gcd(a_i,b_j)=1, gcd(a_k,b_l)=m,$$prove that there exists indices $m,n$ such that $gcd(a_m, b_n)=d$.
This post has been edited 2 times. Last edited by matinyousefi, Apr 7, 2020, 3:46 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
VulcanForge
626 posts
#16
Y by
First note that $\text{gcd} (an+b,cn+d)$ is a divisor of $c(an+b)-a(cn+d) = bc-ad \neq 0$, so it only attains a finite number of values over all $n$. Let the maximum value of $\nu_p(\text{gcd} (an+b,cn+d))$ be $M_p$ for every prime $p$; then we will show that $S$ is the set of all divisors of $N=2^{M_2}3^{M_3}5^{M_5} \cdots$. Obviously every element of $S$ must divide $N$; thus it suffices to show that every divisor of $N$ is in $S$.

Claim: For every prime $p$ (with $M_p>0$) and integer $0 \leq k \leq M_p$, there exists an integer $n$ such that $\nu_p (\text{gcd} (an+b,cn+d)) = k$.

Proof: We induct downwards from $k=M_p$. The base case follows from the definition of $M_p$; now let just assume that the claim is true for $k=\ell$ and we will prove it for $k=\ell-1$. Let $m$ be an integer such that $\nu_p(\text{gcd}(am+b,cm+d))=\ell$, and WLOG let $\nu_p(a) \geq \nu_p(c) = f$. Note that we must have $f < M_p$; otherwise, if $f \geq M_p$, in order to have $\nu_p(\text{gcd}(an+b,cn+d))=M_p$ we must have that $b,d$ are divisible by $p$, which violates the condition $\text{gcd}(a,b,c,d)=1$. Thus the number $x=m+p^{M_p-1-f}$ is an integer; note $$\nu_p(ax+b) \geq \text{min} (\nu_p(am+b),\nu_p(ap^{\ell-1-f})) \geq \ell-1$$$$\nu_p(cx+d) = \text{min}(\nu_p(cm+d), \nu_p(cp^{\ell-1-f})) = \ell-1$$so $\nu_p(\text{gcd}(ax+b,cx+d)) = \ell-1$, completing the induction.

Now note that if $n$ satisfies $\nu_p(\text{gcd}(an+b,cn+d))=k$, then the number $m=n+p^{M_p}$ also satisfies $\nu_p(\text{gcd}(am+b,cm+d))=k$. Thus for every prime $p$ and integer $k \leq M_p$, we can find in infinite arithmetic progression with common difference $p^{M_p}$ such that every term $x$ in the progression satisfies $\nu_p(\text{gcd}(ax+b,cx+d))=k$. This implies by the chinese remainder theorem that for any sequence $a_2, a_3, a_5, a_7, \dots$ with $0 \leq a_i \leq M_i$. we can find some $n$ such that $\text{gcd}(an+b,cn+d)=2^{a_2}3^{a_3}5^{a_5} \cdots$, so every divisor of $N$ is in $S$ as desired.
This post has been edited 3 times. Last edited by VulcanForge, May 18, 2020, 9:38 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jj_ca888
2726 posts
#17
Y by
Notice that if we let $k = \gcd(an + b, cn + d)$ we can write $kx = an + b$ and $ky = cn+d$ for relatively prime $x, y$ and this gives $ad - bc = k(ay - cx)$ hence $k \mid |ad - bc|$. Therefore the set of possible values of the gcd $k$, say $S$, as $n$ ranges across all positive integers is finite.

For any specific prime $p$, let the maximum possible value of $v_p(an + b, cn + d)$ as $n$ ranges be $e_p$. We know by previous steps that the number of positive $e_p$ is finite. Let $M = 2^{e_2}3^{e_3}5^{e_5}\ldots$.

I claim that all factors of $M$ can be hit by $k$ for some $n$. We will prove this by inducting down. The base case is trivial; by definition, $M$ is achievable. For the inductive hypothesis suppose that some $M' \in S$ is achievable by some $n$. We wish to show that for all primes $p \mid M'$, we can find $n$ that achieves $\frac{M'}{p}$. First, write down $\gcd(an + b, cn + d) = M'$ and pick some prime $p \mid M'$ that we are looking to divide by.

Clearly $p \nmid \gcd(a, c)$ or else $p \mid b, d$ contradicting $\gcd(a, b, c, d) = 1$. Let $v_p(M') = e$. Consider $n'$ such that\[n' \equiv n + p^{e - 1} \pmod{p^e}\]\[n' \equiv n \pmod Q\]where $Q$ is some super large prime power of a prime dividing $M$.

We check that indeed $v_p(\gcd(an' + b, cn' + d)) = e-1$ and that due to $n' \equiv n \pmod Q$ the exponents of the other primes do not change, completing our inductive step.

Hence all factors of $M$ are achievable by $k$ for some value $n$, as desired. $\blacksquare$

Blargh
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dchenmathcounts
2443 posts
#18
Y by
oops this is wrong
This post has been edited 1 time. Last edited by dchenmathcounts, Dec 28, 2020, 7:31 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathscienceclass
1241 posts
#19 • 1 Y
Y by Mango247
Note that $ad-bc = -c(an+b)+a(cn+d)$ is a linear combination of $an+b$ and $cn+d$ hence the $\gcd$ divides it. Thus $S$ has a maximum.

Now consider a prime $p$, and let $e_p$ be the maximum value of $\nu_p(an+b, cn+d)$. First we show that if there is $n$ where $k = \nu_p(\gcd(an+b, cn+d))$, then we can get $k-1$ as well. WLOG $\nu_p(a) \ge \nu_p(c)$. Then by taking $n' = n+\frac{p^{k-1}}{\gcd(c, p)}$ we end up with $\nu_p(cn'+d) = \nu_p(cn+d+\frac{cp^{k-1}}{\gcd(c, p)}) = k-1$ because $cn+d$ is a $k$th power of $p$ and $\nu_p(\frac{cp^{k-1}}{\gcd(c, p)}) = k-1$. Additionally $\nu_p(an'+b) = \nu_p(an+b+\frac{ap^{k-1}}{\gcd(c, p)}) \ge k-1$ because $\nu_p(a) \ge \nu_p(c)$ (hence $\nu_p(\frac{ap^{k-1}}{\gcd(c, p)}) \ge k-1$). Thus $\nu_p(\gcd(an'+b, cn'+d)) = k-1$. Using this iteratively says that all $0 \le k \le e_p$ are reachable.

Finally we want to combine prime powers together. We need only show that the sequence $\nu_p(an+b, cn+d)$ is periodic (and that the period is different for each $p$), because we can then use CRT to finish. Note that $\nu_p(\gcd(an+b, cn+d)) = \nu_p(\gcd(a(n+p^{e_p})+b, c(n+p^{e_p})+d))$ so the periodicity is evident (and the periods are relatively prime so no issue there). Thus $S$ contains the divisors of $2^{e_2}3^{e_3}\cdots$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AwesomeYRY
579 posts
#20
Y by
I'm not sure if this works.

Let $M=\frac{|bc-ad|}{\gcd(a,c)}$. I claim that $S$ is the set of divisors of $M$. Firstly, note that
\[\gcd(an+b,cn+d)\mid \frac{c}{\gcd(a,c)}(an+b)-\frac{a}{\gcd(a,c)}(cn+d) = \frac{bc-ad}{\gcd(a,c)}\]Thus, all $x_n=\gcd(an+b,cn+d)$ satisfy $x_n\mid M$. We will only consider $0\leq n \leq M-1$.

Claim 1: I claim that for prime powers $q\mid M$, there are exactly $\frac{M}{q}$ solutions to $q\mid x_n$.

Firstly, note that there exists some smallest solution $n_1 \pmod{q}$ to
\[an+b\equiv 0 \pmod{q}\]because $\gcd(a,q)\mid \gcd(a,M)=1$. Next, note that
\[\frac{c}{\gcd(a,c)}(an+b)\equiv \frac{a}{\gcd(a,c)}(cn+d) \pmod{q}\]Thus, if $an+b\equiv 0$, then we also have $cn_d\equiv 0$. Thus $n_1$ is the only residue mod $q$ that can work, and it does work. Then,we can take $n_1+kq$ which will also work, so there are exactly $\frac{M}{q}$ solutions and we are done.

Using this claim, for any $k\leq v_p(M)$, we can always find some $n$ such that $v_p(x_n)=k$. This $x_n$ is determined by $\pmod{p^k}$. Thus, for any $d\mid M$, by CRT we can construct a $n$ such that for all $p^k=q\mid d$, we have that $v_p(x_n)=v_p(d)$. Thus, this clearly shows that all divisors of $M$ appear 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.
AwesomeYRY
579 posts
#21
Y by
double posted oops. it was the exact same as my previous post (#20)
This post has been edited 6 times. Last edited by AwesomeYRY, May 30, 2021, 5:14 PM
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
#22 • 2 Y
Y by HamstPan38825, rainbow2011
Let $M=\frac{|bc-ad|}{\gcd(a,c)}$. I claim that $S$ is the set of divisors of $M$.
Correct value is actually $M = \frac{|ad-bc|}{\gcd(ad-bc, a^\infty, c^\infty)}$, I believe.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
khina
994 posts
#23
Y by
Another setup problem.

solution sketch
This post has been edited 1 time. Last edited by khina, May 12, 2021, 1:45 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bora_olmez
277 posts
#24
Y by
Quite a cool rigid problem and a problem where one can predict the structure of the final proof.

Solution
This post has been edited 3 times. Last edited by bora_olmez, Aug 14, 2021, 6:39 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8861 posts
#25
Y by
Any suggestions on writeup improvements (or possible flaws) in this proof are greatly appreciated!

First we will show that if for some $p$, if $p^k$ can be attained, then all powers of $p$ less than $p^k$ can be attained.

Case 1. $\gcd(a, p) = 1$ and $\gcd(c, p) = 1$. Then the set of all $n$ such that $p^k$ divides $an+b$ is $i \pmod {p^k}$ for some positive integer $i$, and for $cn+d$ we can define $j \pmod {p^k}$ similarly. There will only exist $n$ such that the gcd is a multiple of $p^k$ if and only if $i=j$. However, this implies that the ``cycles" of $an+b$ and $cn+d$ coincide. In fact $i \equiv j \pmod {p^r}$ for $r \leq k$ must also be true, and since the cycle lengths of $an+b$ and $cn+d$ cycle every $p^r$, they will always coincide after this $i, j$ for all $r \leq k$ as required.

Case 2. $\gcd(a, p) \neq 1$. This implies $p \mid a$. If $p \nmid b$, then none of $an+b$ for any $n$ will be a multiple of $p$. If $p \mid b$, then all $an+b$ will be a multiple of $p$. Thus we can reduce this to $$\frac bp + \frac{an}p.$$If $\frac bp$ and $\frac ap$ are still both multiples of $p$, repeat. If only $p \mid a$, then there are no more factors of $p$. Otherwise, we can move to case 1. (Notice that under these circumstances, we force $\gcd(c, p) = 1$; because $p$ cannot divide all four of $a, b, c, d$. This means that we can always attain the $\nu_p(an+b) = 1, 2, 3, \cdots$ in case 1 in the $cn+d$ side, and thus smaller values of $p^r$ are attainable.)

Next we will show that for relatively prime $m, n$ that are relatively prime, if $x$ and $y$ are elements of $\mathcal S$, then so is $xy$. This is because if the ``cycle" of remainders mod $x$ line up, and the ``cycle" of remainders mod $y$ lines up, then the necessary and sufficient conditions of both are $$n \equiv i \pmod x, n \equiv j \pmod y$$for some $i, j$. Then we can find a unique $n \pmod {xy}$ -- in this case, the GCD will equal $xy$ as required. Note that the converse also holds; we can ``reduce" the condition in the following sense: if for some $x, y$ relatively prime, $xy$ is an element of $\mathcal S$, then there exists some $n$ such that the GCD is $xy$, and the cycles of $an+b, cn+d$ line up mod $x$ and $y$. Therefore, in between the $xy$ terms, we can always find an $n$ such that the GCD is equal to exactly $x$ or exactly $y$.

Next we will show that the set of gcd's is indeed bounded. We will show that for large enough $N$, $N$ cannot be a possible gcd. Notice that if $N$ is a valid gcd, then there exist $k_1, k_2$ such that
\begin{align*}
an+b &= k_1N \\
cn+d &= k_2N.
\end{align*}Equating for $n$ yields $$\frac{k_1N-b}a = \frac{k_2N-d}c \iff N(ck_1-ak_2) = bc-ad.$$The RHS must be a multiple of $N$, but since $bc-ad \neq 0$ and $N$ is sufficiently large, contradiction! Thus proven.
This post has been edited 1 time. Last edited by HamstPan38825, Oct 10, 2021, 2:30 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DottedCaculator
7351 posts
#26
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.
IvoBucata
46 posts
#27
Y by
First note that $gcd(an+b;cn+d)|c(an+b)-a(cn+d)=bc-ad$,so the gcd is bounded.

By the Euclidean algorithm we know that for positive integers $x\geq y$ we have $gcd(x;y)=gcd(y;x-y)$, so after applying this enough times (when $xn+y\geq zn+t$ if $x\geq z$) we are going to reach a place in which (WLOG $a\geq c$) $$gcd(an+b;cn+d)=gcd(cn+d;(a-c)n + b-d)=\cdots = gcd(xn+y;a)$$for some integers $x;y$ and $a$. Here we have $x>1$ and $a\neq 0$ since we already got that the gcd's are bounded. We have $gcd(x,y,a)=1$ since otherwise after going back the steps we are going to get that $gcd(a,b,c,d)>1$, which isn't true. Now let $t$ be the largest divisor of $a$ such that $gcd(t,x)=1$. If $q$ is a prime such that $q|gcd(a,x)$, then $q$ doesn't divide $y$ thus it doesn't divide $gcd(xn+y;a)$. So we always have that $gcd(xn+y;a)|t$. Also since $xn$, and thus $xn+y$, goes trough all residues $(mod t)$ when $n$ varies we get that $gcd(xn+y,a)$ can take all the divisors $mod$ $t$ when $n$ varies 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.
guptaamitu1
656 posts
#28
Y by
v_Enhance wrote:
Claim: Suppose $k_1, k_2 \in S$. Then $\operatorname{lcm}(k_1, k_2) \in S$.

Proof. By the previous claim it suffices to show some multiple of $\operatorname{lcm}(k_1, k_2)$ is in $S$. If $k_1 = \gcd(an_1+b, cn_1+d)$ and $k_2 = \gcd(an_2+b, cn_2+d)$.

We choose $n$ such that: for each prime $p \mid ad-bc$, if $q = p^{\nu_p(bc-ad)}$ then \[ 		n \equiv 		\begin{cases} 			n_1 \pmod q & \nu_p(k_1) \ge \nu_p(k_2)\\ 			n_2 \pmod q & \text{otherwise}. 		\end{cases} 	\]Then $\nu_p(\gcd(an+b, cn+d)) \ge \max(\nu_p(k_1), \nu_p(k_2))$ for each $p$ as desired. $\blacksquare$
Here's a different (brute force) way to prove the Claim (though, the above proof seems nicer);
By previous Claim, it suffices to show $k_1,k_2 \mid f(n)$ for some $n \in \mathbb N$. With $m = \gcd(a,c)$, it is enough to have
$$k_1 \mid m(n - n_1) ~~,~~ k_2 \mid m(n-n_2)$$Let $p_1 = k_1 \div \gcd(k_1,m)$ and $p_2 = k_2 \div \gcd(k_2,m)$. We want
$$p_1 \mid n - n_1 ~~,~~ p_2 \mid n - n_2$$Which is further equivalent to
$$\gcd(p_1,p_2) \mid n_1 - n_2$$Let $l = \gcd(p_1,p_2)$. Then
$$l \mid an_1 + b , cn_1 + d,an_2 + b,cn_2 + d$$Which gives
$$l \mid a(n_1 - n_2), c(n_1 - n_2) \implies l \mid m(n_1 - n_2)$$As $\gcd(m,p_1) = \gcd(m,p_2) = 1$ (just by definition of $p_1,p_2$), so $\gcd(l,k) = 1$. Thus $l \mid n_1 - n_2$, as desired.
This post has been edited 1 time. Last edited by guptaamitu1, Feb 13, 2022, 8:35 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Knty2006
50 posts
#29 • 1 Y
Y by banterbry
Claim: $|S|$ is bounded

Proof:

$$(an+b,cn+d) \leq gcd(an+b,anc+ad)$$$$=gcd(an+b, anc+ad-anc-bc)$$$$=gcd(an+b,ad-bc)$$
This means that all the terms in $S$ must divide $ad-bc$

Therefore, the size of $S$ is clearly bounded

Subclaim:If $x$ is in $S$, all the factors of $x$ are also in $S$

Proof:

Suppose some prime $p$ divides $x$ and $V_p(x)=k$,
set a new number $x'$ such that
$$x' \equiv p^{k-1} (\mod p^k)$$$$x' \equiv x ( \mod j^{V_j(ab-cd)})$$
for all prime $j$ dividing $ab-cd$ , where $j$ and $p$ are distinct
Now, observe that by CRT, such an $x'$ must exist

Claim: If $x_1$ and $x_2$ are in $S$, then $LCM(x_1,x_2)$ is in $S$

Proof:
Let $x_1=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$

$x_2=p_1^{b_1}p_2^{b_2}...p_n^{b_n}$

For some prime $p_i$, if $a_i>b_i$ take $k$ such that
$$k \equiv x_1(\mod p_i^{a_i})$$
Similarly, do this for all the $i$
By CRT, we can construct such a $k$

Observer that $LCM (x_1,x_2) |k$

Which means that there must exist some multiple of $LCM(x_1,x_2)$ in $S$

But using our subclaim, we know that all the factors of the multiple of the $LCM(x_1,x_2)$ are in $S$, this includes $LCM(x_1,x_2)$. Therefore, our claim is true .

Claim: All the terms in $S$ are exactly all the divisors of $\max {S}$

Proof:
By our first claim , we know that a maximum number exists in $S$
Let the largest term in $S$ be $m$

By our claim 2, the $LCM$ of $m$ and any other term in $S$ must exist within $S$. But note that the $LCM \geq m$, but by definition we know that there cannot exist a term larger than $m$ within $S$

Therefore, all the $LCM$ including $m$ must exactly be $m$. Hence, every other term in $S$ must be a factor of $m$.

Combining this together with our earlier subclaim, we can conclude that all the terms in $S$ are exactly all the divisors of $m$
This post has been edited 1 time. Last edited by Knty2006, Sep 20, 2022, 12:55 AM
Reason: stupid
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackbluecar
303 posts
#30 • 4 Y
Y by Mango247, Mango247, Mango247, ihatemath123
(Just a sketch) By the euclidean algorithm we have \[ \gcd(an+b,cn+d) = \gcd(an+b,(a-b)n+(c-d) = \cdots = \gcd(\ell(n),M) \]For some linear function $\ell$ and a positive integer $M$. Notice that this implies $S$ is bounded since any element in $S$ must divide $M$. Now, assume that $\gcd(\ell(n),M)$ obtains maximum value an an integer with prime factorization $p_1^{\alpha_1} \cdots p_k^{\alpha_k}$. By CRT we can choose $\ell$ so that $\nu_{p_i}(\ell(n)) = \beta_i$ for any sequence of non-negative integers $\beta_1,\beta_2, \ldots, \beta_k$ obeying $\beta_i \leq \alpha_i$. Notice that these are also the only possible values that $\gcd(\ell(n),M)$ by maximality. So, $S$ is exactly the set of divisors of $p_1^{\alpha_1} \cdots p_k^{\alpha_k}$. $\blacksquare$
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
#32 • 1 Y
Y by centslordm
Different solution, I think?

Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
huashiliao2020
1292 posts
#33
Y by
no latex sol :rotfl:

Note that gcd(an+b,cn+d)|c(an+b)-a(cn+d)=bc-ad, so S is bounded; by suitably using euclidean algorithm we can get a linear gcd(an+b,cn+d)=gcd(cn+d,(a-c)n + b-d)=...=gcd(mn+x,y), with $y\ne 0$, and if m=0, we're done since there's only one number, while if m=1, this runs over all divisors of a, so henceforth assume m>1, and assume gcd(m,x,y)=1 (otherwise divide by this suitably since it's always there). Taking l as the largest divisor of y with gcd(m,l)=1, and a prime power p|gcd(m,y), p doesn't divide gcd(mn+x,y) implies gcd(mn+x,y)|l|y (since any other prime power factors of y are relatively prime to the gcd); since m is relatively prime to l, varying n goes over all residues mod l, so the set S goes over all divisors of l!
This post has been edited 4 times. Last edited by huashiliao2020, Sep 7, 2023, 6:13 PM
Reason: Better
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
198 posts
#35
Y by
Note that $\gcd(an + b, cn + d) \mid c(an + b) - a(cn + d) = bc - ad$, so $S$ is finite. Let $M$ be maximum element in $S$, and let $M = p_1^{\alpha_1}p_2^{\alpha_2} \dots p_k^{\alpha_k}$. Fix arbitrary $0 \le \beta_{i} \le \alpha_{i}$ and we'll prove that there exists $n$ such that $\nu_{p_i}(\gcd(an + b, cn + d)) = \beta_i$ for all $i$.

Since $\gcd(a, b, c, d) = 1$, so WLOG we can assume $\nu_{p_i}(a) = 0$ or $\nu_{p_i}(b) = 0$. If $\nu_{p_i}(b) = 0$ and $\nu_{p_i}(a) > 0$, then $\nu_{p_i}(an + b) = 0$, so $\nu_{p_i}(M) = 0$, a contradiction.
Thus we can assume $\nu_{p_i}(a) = 0$.

Now taking $n \equiv \frac{p_i^{\beta_i} - b}{a} (p_i^{\beta_i})$ by CRT, we have $an + b \equiv p_i^{\beta_i} (p_i^{\beta_i + 1})$ for all $i$ and it's not hard to see that $p_i^{\beta_i} \mid cn + d$. So $\gcd(an + b, cn + d) = p_1^{\beta_1}p_2^{\beta_2} \dots p_k^{\beta_k}$. $\blacksquare$
This post has been edited 1 time. Last edited by thdnder, Dec 9, 2023, 6:07 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Leo.Euler
577 posts
#36
Y by
We operate on the matrix $M_0 = \begin{bmatrix} a & c \\ b & d \end{bmatrix}$ using the transforms \[ T_1 = \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix} \]\[ T_2 = \begin{bmatrix} 1 & 1 \\ -1 & 0 \end{bmatrix} \]\[ T_3 = \begin{bmatrix} 1 & 1 \\ 0 & -1 \end{bmatrix} \]\[ T_4 = \begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} \]all of which have determinant $\pm 1$. Thus, upon application of these transforms, $|ad-bc|$ is invariant. Moreover, $\gcd(an+b,cn+d)$ is also preserved for fixed $n$ by the Euclidean algorithm, so $S$ is preserved as well. Apply these transformations to bring $a$ to $0$ by following the Euclidean algorithm. Then it suffices to prove the result when $a=0$. We need to show that if $\gcd(b, c, d)=1$ for integers $b$, $c$, and $d$ with $bc \neq d$, then the set of all possible values of $\gcd(b, cn+d)$ over all positive integers $n$ is the set of positive integer divisors of some positive integer. WLOG $\gcd(c, d)=1$ by scaling. By Bezout's identity, it is easy to see that $S$ is a subset of the divisors of \[ m := \frac{b}{\gcd(b, c^{\infty})}. \]By CRT, it can be shown that all divisors of $m$ can be constructed, and we conclude.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ezpotd
1266 posts
#37
Y by
not sure if this works.. but if it does its a cool sol

Strong induct on $\max (a,c)$. The base of $a = c = 1$ is obviously true. For the inductive hypothesis, WLOG let $a \geq c$, consider $\gcd(an + b, cn + d) = \gcd(cn + d, (a -c)n + (b - d)) $. We divide into two cases.

Case 1: $a = c$. Then we get the desired expression as $\gcd(cn + d, b - d)$. For all primes $p$, we show that the set of $\nu_p(\gcd(cn +d, b-d))$ is of the form $0 \cdots x_p$, and then use CRT to conclude the expression ranges over all divisors of some number $\prod p^{x_p}$. Consider any prime $p$ dividing $b - d$, then we consider $\nu_p(b - d), \nu_p(d), \nu_p(c)$. Observe that $\gcd(b,c,d) = 1$, so if both $c,d$ divide some prime, then $b$ cannot and thus it cannot be part of the $gcd$ since it won't divide $b - d$. Otherwise, if $c$ doesn't divide the prime, we can also have $\nu_p(cn + d)$ as unbounded, so $\nu_p(\gcd(cn + d, b - d))$ can range anywhere from $0$ to $\nu_p(b-d)$. If $c$ does divide the prime, then $d$ can't and we are actually forced that $\nu_p(cn + d) = 0$.

Case 2: $a \neq c$. Then it remains to show that we can apply the inductive hypothesis on $\gcd(cn + d, (a -c)n + (b - d)) $. To do this, we must show $c(b - d) \neq d(a - c)$, which is trivial since it reduces to $ad \neq bc$, and we must show $\gcd (c, d, a - c, b - d) = 1$, which is also trivial since $\gcd(c,d, a-  c, b -d ) = \gcd(\gcd(c , a - c), \gcd (d, b -d)) = \gcd(\gcd(a,c) , \gcd(b, d)) = \gcd(a,b,c,d) =1$.
This post has been edited 2 times. Last edited by ezpotd, Jul 12, 2024, 11:24 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ywgh1
139 posts
#38
Y by
RMM 2018
Nice problem, Here is a sketch:

Firstly we have that.
$$gcd(an+b,bn+c)| bc-ad$$Hence we get that $S$ is finite, now we show all divisors are in $S$.

Let $N=p_1^{a_1} \dots p_k^{a_k}$, be the maximal element of $S$.
Then we show that $\nu_{p_i}(\gcd(an + b, cn + d)) = a_i$.

We can see that $\nu_{p_i}(a)$ and $\nu_{p_i}(b)$ both equal $0$ then this implies that both $\nu_{p_i}(d)$ and $\nu_{p_i}(c)$ more than $0$. We give the construction $$n = \frac{p_i^{a_i} - b}{a} (p_i^{a_i})$$hence all divisors are in $S$
This post has been edited 1 time. Last edited by Ywgh1, Sep 12, 2024, 7:48 PM
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
#39
Y by
Let $a=gr,c=gs$ where $\gcd(r,s)=1$. Then, perform Euclidean algorithm on the matrix
$$\begin{bmatrix}
    gr & b\\
    gs & d
\end{bmatrix}$$to get
$$\begin{bmatrix}
    g & u\\
    0 & v
\end{bmatrix}.$$Thus $\gcd(grn+b,gsn+d)=\gcd(gn+u,v)$. Note that $\gcd(u,v)=\gcd(b,d)$ as well. Since the determinant of the matrix didn't change, $gv=ad-bc$, so $v\neq 0$ as $ad-bc\neq 0$. Clearly, the gcd divides $v$. Consider any maximal prime power $p^k\mid v$ for $k\geq 1$.

If $p\nmid g$, then $gn+u$ will cycle through all residues mod $p^k$, so the exponent of $p$ in $gn+u$ will hit every possible value from $0$ up to $k$. Call this a Category 1 prime.

If $p\mid g$, then we claim that $p\nmid u$. Suppose FTOSC that $p\mid u$ as well. Then, $p$ would divide both $u$ and $v$, but because $\gcd(b,d)=\gcd(u,v)$, $p$ would divide both $b$ and $d$ as well. Since $p$ already divides both $a$ and $c$, this contradicts $\gcd(a,b,c,d)=1$. Thus, in this situation, as $p\mid g$ but $p\nmid u$, $gn+u$ is never divisible by $p$ at all. Call this a Category 2 prime.

By Chinese Remainder Theorem, this means that the possible values of $\gcd(gn+u,v)$ are exactly divisors of $v$ that consist of only Category 1 prime divisors, as we know any prime exponent up to the maximum is possible, and by CRT we can select any combination of them.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
OronSH
1738 posts
#40
Y by
First $S$ is finite since $m\mid an+b,cn+d\implies m\mid bc-ad$. Now letting $A,B\in S$ we claim some element of $S$ is at least $\operatorname{lcm}(A,B)$. To do this if $A\mid an_1+b,cn_1+d,B\mid an_2+b,cn_2+d$ then choose $A',B'$ such that $A'\mid A,B'\mid B,\gcd(A',B')=1$ and $A'B'=\operatorname{lcm}(A,B)$. Then choose $n\equiv n_1\pmod{A'},n_2\pmod{B'}$ and $\operatorname{lcm}(A,B)=A'B'\mid an+b,cn+d$. In particular if $K$ is the largest element of $S$ then all other elements of $S$ are factors of $K$ as otherwise we would have an element larger than $K$.

Now we show all factors of $K$ are in $S$. Let $K\mid an_1+b,cn_1+d$. Note that for $p\mid K$ we have $p$ does not divide at least one of $a,c$ as otherwise $p\mid a,b,c,d$, impossible. Then for any $d\mid K$ choose $n\equiv n_1+p^j\pmod{p^i}$ where $i,j=\nu_p(K),\nu_p(d)$. This guarantees $p^i\mid an+b,cn+d$ but $p^{i+1}$ does not divide one of them. Thus choosing this across all $p$ finishes.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ilikeminecraft
623 posts
#41
Y by
We will say the number $n$ generates $x$ if $(an + b, cn + d) = x.$

We have that $(an + b, cn + d) = \frac{(an + b, acn + ad)}{(a, b)} = \frac{(an + b, ad - bc)}{(a, b)}.$ Hence, $S$ is finite.

Let $k\in S.$ Let $p\mid k.$ I claim that $\frac kp \in S.$

Let $n$ generate $k$. Let $x = \nu_p(k).$ I claim that $n'$ satisfying:
\begin{align*}
  n' \equiv & n + p^{x - 1}\pmod {p^{x}} \\
  n' \equiv & n \pmod{\frac k{p^x}}
\end{align*}satisfies our claim. Note that $n'$ exists by CRT. Notice that $\nu_p(an' + b) = x - 1$ while $\nu_p(cn' + d) \geq x -1,$ and so $\nu_p(\gcd(an' + b, cn' + d)) = x - 1.$ Clearly, all other ones don't change. Hence, our claim is true. Hence, we can also state that $n$ generates $x$ if $x\mid(an + b, cn + d)$

Now I claim that $S$ is a closed under the LCM operation. We denote the lcm of $a, b$ as $[a, b].$ Let $n_1$ generate $x$ and $n_2$ generate $y.$ We pick $n$ such that for each $p\mid ad - bc$ and $q = p^{\nu_p(ad - bc)}$:
\[ n \equiv \begin{cases} n_1 \pmod q & \nu_p(x) \ge \nu_p(y)\\ n_2 \pmod q & \text{otherwise}. \end{cases} \]This forces $[x, y]\mid n.$ Thus, we are done.
Z K Y
N Quick Reply
G
H
=
a