Set closed under lcm(a,b)/(b-a)

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Set closed under lcm(a,b)/(b-a)

G H J

Reveal topic tags

extremal principle

L

G H BBookmark kLocked kLocked NReply

Source: 2021 Thailand MO P9

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1593 posts

#1 h Nov 29, 2021, 2:48 AM • 1 Y

Y by HWenslawski

Let $S$ be a set of positive integers such that if $a$ and $b$ are elements of $S$ such that $a<b$ , then $b-a$ divides the least common multiple of $a$ and $b$ , and the quotient is an element of $S$ . Prove that the cardinality of $S$ is less than or equal to $2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#2 h Nov 29, 2021, 5:19 PM • 1 Y

Y by HWenslawski

MarkBcc168 wrote:

Let $S$ be a set of positive integers such that if $a$ and $b$ are elements of $S$ such that $a<b$ , then $b-a$ divides the least common multiple of $a$ and $b$ , and the quotient is an element of $S$ . Prove that the cardinality of $S$ is less than or equal to $2$ .

Call such a set "special".Moreover let $f(a,b)=\frac{\text{lcm}(a,b)}{a-b}$ where $a>b$
We claim that no special set can contain $3$ elements.
Suppose such an set $\mathcal{S}=\{a_1>a_2>a_3 \}$ exists.
WLOG $\gcd(a_1,a_2)=d>1$ (the condition $d=1$ gives the pair $\{2,z_1,2z_2 \}$ with $z_1$ odd which doesn't work).
First of all note that this gives $a_1=\frac{k_1k_2}{k_1-k_2}$ with $a_1=dk_1,a_2=dk_2$ .Note that $\gcd(a_3,d)=1$ and let $d_2=\gcd(a_1,k_2)$ and $d_3=\gcd(a_1,k_3)$ .
Now note that $a_2<f(a_1,a_3)=\frac{\frac{k_1k_2}{d_2(k_1-k_2)} \cdot k_1}{\frac{k_1^2-2k_1k_2}{k_1-k_2}}<a_1 \not\in \mathcal{S}$ so this holds.

Induction. finishes.

This post has been edited 3 times. Last edited by Sprites, Dec 7, 2021, 5:38 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12 posts

txc

#3 h Nov 30, 2021, 2:32 AM • 2 Y

Y by mijail, Quidditch

Suppose such a set $S$ exists.
Lemma. For any $a<b,a,b\in S$ , we have $\frac{b}{a}=1+\frac{1}{k_1}$ for some $k_1\in\mathbb{N}$ , and $k_1(k_1+1)\in S$ .

Let $d=\gcd(a,b), a=k_1d,b=k_2d$ . We have $\frac{\text{lcm}(a,b)}{b-a}=\frac{k_1k_2}{k_2-k_1}\in\mathbb{Z}.$ But since $\gcd(k_1,k_2)=1,\gcd(k_1k_2,k_2-k_1)=1$ , we must have $k_2-k_1=1$ , which gives the above lemma.

Since $\frac{b}{a}\leq 1+\frac{1}{1}=2$ for any $a<b,a,b\in S$ , $S$ must be finite. Let the elements of $S$ be $a_1<a_2<\dots<a_n$ for some $n\geq 3$ .

Case 1. $\frac{a_3}{a_2}=\frac{a_2}{a_1}=1+\frac{1}{k}$ .
Then $\frac{a_3}{a_1}=\left(1+\frac{1}{k}\right)^2=1+\frac{2k+1}{k^2}=1+\frac{1}{l}$ for some $l\in\mathbb{N}$ , so $2k+1\mid k^2$ , a contradiction.

Case 2. $\frac{a_3}{a_2}\neq\frac{a_2}{a_1}$ .
Then the $n$ numbers $\frac{a_3}{a_2},\frac{a_2}{a_1},\frac{a_3}{a_1},\frac{a_4}{a_1},\frac{a_5}{a_1},\dots,\frac{a_n}{a_1}=1+\frac{1}{k}$ are all distinct. By the lemma, each distinct value of $\frac{a_j}{a_i}$ requires a distinct number of the form $m(m+1)$ in $S$ , so all $n$ elements are of the form $m(m+1)$ .
In particular, $a_1=k(k+1)$ since $\frac{a_n}{a_1}$ is the largest among the $n$ fractions. But then $a_n=k(k+1)\left(1+\frac{1}{k}\right)=(k+1)^2$ cannot be of the form $m(m+1)$ , a contradiction. $\Box$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

159 posts

puntre

#4 h Mar 10, 2022, 3:43 PM • 1 Y

Y by Quidditch

Can't do it during the competition and figures it out a couple of months later. :blush:

:blush:

Assume for the sake of contradiction that $|S|\geq 3.$
Claim: $b-a|\text{lcm}[a,b]\implies \text{gcd}(a,b)=b-a$ .
Proof: Let $b_1=b-a,$ and $a=da'$ , $b_1=db_1'$ where $d\in\mathbb{N}$ and $\gcd(a,b_1)=1$ . Then $b-a|\frac{ab}{\gcd(a,b)}\implies d^2b_1'|d^2(a')^2\implies b_1=1\implies\gcd(a,b_1+a)=b_1$ Hence $\gcd(a,b)=b-a.$

Using the claim, we conclude that $a,b\in S\implies \frac{ab}{(a-b)^2}\in S$ .
Let $m<n$ be two smallest elements of $S$ . Clearly, $\frac{mn}{(m-n)^2}\in S$ , which implies that $\frac{(n)(\frac{mn}{(m-n)^2})}{(n-\frac{mn}{(m-n)^2})^2}\in S\implies A=\frac{m}{(n-m)^2+\frac{m^2}{(n-m)^2}-2m}\in S.$ But $A$ is smaller than $n$ leads to a contradiction. So we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a