a problem from Russia Olympiad 2001

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

a problem from Russia Olympiad 2001

G H J

Reveal topic tags

L

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.

469 posts

#1 h Jun 12, 2009, 1:17 AM • 4 Y

Y by itslumi, HWenslawski, MetaphysicalWukong, Adventure10

Let $a,b$ be $2$ distinct positive interger number such that $(a^2+ab+b^2)|ab(a+b)$ . Prove that: $|a-b|>\sqrt [3] {ab}$ .

Z K Y

The post below has been deleted. Click to close.

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

750 posts

#2 h Jun 12, 2009, 2:24 AM • 6 Y

Y by Fermat_Theorem, programjames1, Andrei246, HWenslawski, Adventure10, ehuseyinyigit

mathVNpro wrote:

Let $a,b$ be $2$ distinct positive interger number such that $(a^2 + ab + b^2)|ab(a + b)$ . Prove that: $|a - b| > \sqrt [3] {ab}$ .

$(a^2+ab+b^2)|ab(a+b) \Leftrightarrow \begin{cases} (a^2+ab+b^2)|a(a^2+ab+b^2)-ab(a+b) \\ (a^2+ab+b^2)|b(a^2+ab+b^2)-ab(a+b) \end{cases}$

$\Leftrightarrow \begin{cases} (a^2+ab+b^2)|a^3 \\ (a^2+ab+b^2)|b^3 \end{cases}$

$\Rightarrow (a^2+ab+b^2)| \gcd(a^3,b^3)=(\gcd(a,b))^3=(\gcd(a, |a-b|))^3 \le |a-b|^3$

So $|a-b| \ge \sqrt[3]{a^2+ab+b^2}>\sqrt[3]{ab}$

Z K Y

The post below has been deleted. Click to close.

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

599 posts

#3 h Jun 12, 2009, 10:42 AM • 3 Y

Y by Prof.Shanku, Adventure10, Mango247

mathVNpro wrote:

Let $a,b$ be $2$ distinct positive interger number such that $(a^2 + ab + b^2)|ab(a + b)$ . Prove that: $|a - b| > \sqrt [3] {ab}$ .

Let $a=px,b=py$
Then we have that:
$x^2+y^2+xy|pxy(x+y)$
But $(x^2+y^2+xy,x)=1,(x^2+y^2+xy,y)=1,(x^2+y^2+xy,x+y)=1$
So $x^2+y^2+xy|p$
$p \ge x^2+y^2+xy$ $\boxed{1}$

We have to prove that:
$p^3|(x-y)| >p^2xy \Leftrightarrow p|(x-y)| >xy$

But $|(x-y)| >0$ ,so we finally have to prove that

$p>xy$ ,which follows from the $\boxed{1}$

Z K Y

The post below has been deleted. Click to close.

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

4216 posts

#4 h Jul 10, 2012, 5:29 PM • 4 Y

Y by Navi_Makerloff, pavel kozlov, Adventure10, Mango247

Another solution:

$a^{2}+ab+b^{2}|ab(a+b) \implies a^{2}+ab+b^{2}\leq ab(a+b)$
We see that equality cannot hold because that implies $a=b$ which contradicts the problem statement.

So we have
$\begin{align*} a^{2}+ab+b^{2}&<ab(a+b) \\ \frac{a^3-b^3}{a-b}&<ab(a+b) \\ a^3-b^3&<ab(a^2-b^2) \\ a^3-3a^2b+3ab^2-b^3&<ab(a^2-b^2-3a+3b) \\ (a-b)^3&<ab(a^2-b^2-3a+3b) \\ (b-a)^3&>ab(b^2-a^2+3a-3b) \\ b-a&>\sqrt[3]{ab(b^2-a^2+3a-3b)} \end{align*}$
WLOG let $b>a$ , we have $\sqrt[3]{ab(b^2-a^2+3a-3b)}=\sqrt[3]{ab(b(b-3)-a(a-3))}>\sqrt[3]{ab}$ so $b-a=|a-b|>\sqrt[3]{ab}$ .

Z K Y

The post below has been deleted. Click to close.

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

676 posts

#5 h Mar 25, 2013, 6:50 AM • 3 Y

Y by Illuzion, Adventure10, Mango247

mathVNpro wrote:

Let $a,b$ be $2$ distinct positive interger number such that $(a^2+ab+b^2)|ab(a+b)$ . Prove that: $|a-b|>\sqrt [3] {ab}$ .

Let $d=(a,b)$ so let $a=dx$ and $b=dy$ where $(x,y)=1$
So now we have
we have
$\frac{dxy(x+y)}{x^2+y^2+xy} \in Z$
now note that $(x^2+y^2+xy,x) =1 , (x^2+y^2+xy,y)=1$ and similarly since $(x+y,y)=1$ we have
$(x^2+y^2+xy , x+y)=(y^2,x+y) = 1$ .
since it is a integer , we have $x^2+xy+y^2 | d$ so $d \ge x^2+xy+y^2$
so
$(|a-b|)^3 = (|dx-dy|)^3 = d^3(|x-y|)^3 \ge d^2 \cdot d \ge d^2(x^2+y^2+xy) > d^2(xy) = (dy)(dy) = ab$
So we are done $\Box$

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#6 h Oct 18, 2018, 7:42 PM • 3 Y

Y by A-Thought-Of-God, Adventure10, Mango247

Note that $a^2+ab+b^2\mid a(a^2+ab+b^2)-ab(a+b)=a^3$ , and similarly $a^2+ab+b^2\mid b^3$ , so $a^2+ab+b^2\mid \gcd(a^3,b^3)=\gcd(a,b)^3$ . Thus,
$a^2+ab+b^2\le \gcd(a,b)^3\le |b-a|^3.$ Thus, $ab<|b-a|^3$ , so $|a-b|>\sqrt[3]{ab}$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

1218 posts

#8 h Oct 19, 2018, 5:14 PM • 4 Y

Y by Maths_Guy, A-Thought-Of-God, Adventure10, Mango247

Let $\gcd(a,b)=g$ . Take $a=gc$ and $b=gd$ , where $\gcd(c,d)=1$ . Then the problem condition gives that $c^2+cd+d^2 \mid g \cdot cd(c+d)$

Now, $1=\gcd(c,d)=\gcd(c^2,d)=\gcd(c^2+d(c+d),d)=\gcd(c^2+cd+d^2,d)$ Similarly, we get that $\gcd(c^2+cd+d^2,c)=1$ . Also, $1=\gcd(c,d)=\gcd(c+d,d)=\gcd(c+d,d^2)=\gcd(c+d,d^2+c(c+d))=\gcd(c^2+cd+d^2,c+d)$ Thus, We have $c^2+cd+d^2 \mid g$ $\Rightarrow g \geq c^2+cd+d^2>cd$ . Multiplying both sides by $g^2$ , we get that $g^3>g^2cd=ab$ . Hence, $|a-b|^3=g^3|c-d| > g^3 >ab \Rightarrow |a-b|>\sqrt [3] {ab} \text{ } \blacksquare$

This post has been edited 3 times. Last edited by math_pi_rate, Oct 20, 2018, 4:22 AM
Reason: Edited @below

Z K Y

The post below has been deleted. Click to close.

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

3042 posts

#9 h Oct 19, 2018, 6:04 PM • 2 Y

Y by Adventure10, Mango247

math_pi_rate wrote:

$c^2+cd+d^2 \mid gcd(c+d)$

What do you mean by $\gcd(c+d)$ ?

This post has been edited 1 time. Last edited by TheDarkPrince, Oct 19, 2018, 6:04 PM

Z K Y

The post below has been deleted. Click to close.

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

211 posts

#10 h Oct 19, 2018, 6:23 PM • 2 Y

Y by Adventure10, Mango247

TheDarkPrince wrote:

math_pi_rate wrote:

$c^2+cd+d^2 \mid gcd(c+d)$

What do you mean by $\gcd(c+d)$ ?

Perhaps he means $g*c*d*(c+d)$ .

Z K Y

The post below has been deleted. Click to close.

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

3042 posts

#11 h Oct 19, 2018, 6:32 PM • 2 Y

Y by Illuzion, Adventure10

Illuzion wrote:

Perhaps he means $g*c*d*(c+d)$ .

Oops maybe

A better choice of variables would have been better

Z K Y

The post below has been deleted. Click to close.

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

1218 posts

#12 h Oct 20, 2018, 4:20 AM • 2 Y

Y by Adventure10, Mango247

TheDarkPrince wrote:

math_pi_rate wrote:

$c^2+cd+d^2 \mid gcd(c+d)$

What do you mean by $\gcd(c+d)$ ?

It meant $g \cdot cd$ . Sorry for the mistake. Corrected it.

Z K Y

The post below has been deleted. Click to close.

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

1492 posts

#13 h May 19, 2020, 7:30 AM

Y by

Took me a solid 30 minutes to realize $ab < a^2 + ab + b^2$ .

Set $a \ge b.$ Notice that $a^2 + ab + b^2 \mid a(a^2 + ab + b^2) - ab(a + b) = a^3$ , and likewise. $a^2 + ab + b^2 \mid b^3.$ Therefore, we have $a^2 + ab + b^2 \mid \gcd(a, b)^3.$ Now, $\gcd(a, b)^3 = \gcd(a-b, b)^3 \le (a-b)^3.$ Moreover, we have that $ab < a^2 + b^2 + ab \le (a-b)^3$ so we conclude.

Z K Y

The post below has been deleted. Click to close.

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

548 posts

#14 h Dec 2, 2020, 2:04 AM

Y by

Let $a=dm$ and $b=dn$ , where $d=\gcd(a,b)$ . Hence, $\gcd(m,n)=1$ . Substituting into the given,
$d^2m^2+d^2mn+d^2n^2 | d^3mn(dm+dn) \implies m^2+mn+n^2 | dmn(m+n)=.$
I claim that $\gcd(m^2+mn+n^2, mn(m+n))=1$ . To see this, it suffices to prove that $\gcd(m, m^2+mn+n^2)=\gcd(n, m^2+mn+n^2)=\gcd(m+n, m^2+mn+n^2)=1$ . The first two are trivial. For the third one, note that $\gcd(m+n, m^2+mn+n^2)=\gcd(m+n, (m+n)^2-mn)=1$ (since $m$ and $n$ are relatively prime).

Hence, we have $m^2+mn+n^2 | d,$ which means that $m^2+mn+n^2 \leq d$ . Then,
$m^2+mn+n^2 \leq d \implies \frac{a^2}{d^2}+\frac{ab}{d^2}+\frac{b^2}{d^2} \leq d \implies a^2+ab+b^2 \leq d^3.$ However, it is easy to see that $d^3 \leq |a-b|^3,$ so $|a-b|^3 \geq a^2+ab+b^2 > ab.$ Taking the cube root of $|a-b|^3 > ab$ , 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.

484 posts

554183

#15 h Aug 6, 2021, 4:56 PM

Y by

WLOG $a \geq b$
$a^2+ab+b^2|ab(a+b)=a^2b+ab^2 \iff a^2+ab+b^2|a^3, b^3 \implies a^2+ab+b^2|d^3$ where $d=(a,b)$ . Also let $a=dx, b=dy, (x,y)=1$ of course.
So we have $d \geq x^2+xy+y^2$ . $|a-b|>\sqrt [3] {ab} \iff d(x-y)^3 > xy$ which follows easily since $d(x-y) \geq x^2+xy+y^2 \geq 3xy > xy$

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#16 h Oct 29, 2021, 10:47 PM • 1 Y

Y by centslordm

Let $a=kA,b=kB$ where $k=\gcd(a,b)$ , so $\gcd(A,B)=1$ . The condition is equivalent to
$k^2(A^2+AB+B^2) \mid k^3AB(A+B) \implies A^2+AB+B^2 \mid kAB(A+B).$ Now, $\gcd(A^2+AB+B^2,A)=\gcd(B^2,A)=1$ , and likewise $\gcd(A^2+AB+B^2,B)=\gcd(A^2,B)=1$ , so we actually have
$A^2+AB+B^2 \mid k(A+B).$ This means that $\tfrac{A^2+AB+B^2}{A+B} \leq k$ . Now, since $a \neq b$ , we have $|a-b|\geq k$ , so it suffices to prove that
$k \geq \frac{A^2+AB+B^2}{A+B} > \sqrt[3]{AB}.$ I will actually prove this for any positive reals $A,B \geq 1$ . Indeed, rewrite the inequality as
$(A+B)^2>(A+B)\sqrt[3]{AB}+AB.$ For a fixed value of $A+B$ , $AB$ is maximized at $A=B$ , which maximizes the RHS but keeps the LHS constant. Hence we only need to consider $A=B=x$ . In this case, the inequality becomes
$4x^2>2x^{5/3}+x^2 \iff x^{1/3}>\frac{2}{3},$ which is certainly true, implying $|A-B|>\sqrt[3]{ab}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1080 posts

#19 h Dec 24, 2021, 6:09 AM • 1 Y

Y by centslordm

Let $\gcd(a,b)=d,$ $a=dx,$ and $b=dy.$ Let $z=x^2+xy+y^2$ and we see that $z\mid dxy(x+y).$ But $\gcd(x,z)=\gcd(y,z)=\gcd(x+y,z)=1$ so $z\mid d.$ Hence, $a^2+ab+b^2\mid d^3$ so $ab<a^2+ab+b^2\le d^3\le (a-b)^3$ and we are done. $\square$

Z K Y

The post below has been deleted. Click to close.

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

365 posts

#20 h Apr 18, 2023, 5:29 PM

Y by

Once you get $a^2+ab+b^2 \mid a^3$ and $a^2+ab+b^2 \mid b^3$

WLOG $a \geq b$ . Note that $(a-b)^3 = a^3-b^3-3ab(a+b) = a^3-b^3-3ab(a+b)+6ab^2$ so $a^3-b^3-3ab(a+b) = (a-b)^3-6ab^2$ which implies $a^2+ab+b^2 \mid (a-b)^3-6ab^2$
If $(a-b)^3 = 6ab^2$ then $a-b = \sqrt[3]{6ab^2} > \sqrt[3]{ab}$ . If $(a-b)^3-6ab^2 \neq 0$ then $(a-b)^3-6ab \geq a^2+ab+b^2$ $(a-b)^3 \geq a^2+b^2+6ab^2+ab > ab$ which means $a-b > \sqrt[3]{ab}$ .

This post has been edited 2 times. Last edited by andyxpandy99, Apr 18, 2023, 6:08 PM

Z K Y

The post below has been deleted. Click to close.

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

593 posts

#21 h Jun 2, 2023, 1:44 AM

Y by

Let gcd(a,b) = d, and a=dx, b=dy. WLOG, let a>b which implies x>y. Plugging this in, we get $d^2(x^2+xy+y^2)|d^3xy(x+y)$ simplifying to $x^2+xy+y^2|d(xy)(x+y)$ . We can easily prove that $\gcd(x^2+xy+y^2,xy) = 1$ (by letting p divide both numbers and arriving at a contradiction). By this fact, we can easily arrive to the fact that $\gcd(x^2+xy+y^2,xy) = 1$ and $\gcd(x^2+xy+y^2,x+y)=1$ , so $x^2+xy+y^2|d$ . Therefore, $d \geq x^2+xy+y^2$ , meaning $|a-b|>\sqrt [3] {ab}$ , or $d^3(x-y)^3 >xy$ is true as $x-y \geq 1$ and $d^3$ is clearly greater than $xy$ .

Z K Y

The post below has been deleted. Click to close.

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

chakrabortyahan

384 posts

chakrabortyahan

#22 h Oct 24, 2023, 12:23 PM

Y by

Nice problem..
Let $a=gx$ and $b=gy$ where $x$ and $y$ are coprime to each other.
$\begin{align*} a^2+ab+b^2 &\mid ab(a+b) \\ g^2 (x^2+xy+y^2) &\mid gx\cdot gy \cdot (gx+gy) \end{align*}$ Now note that as $\text{gcd}(x,y) = 1 \implies \text{gcd}(x,x+y) = 1\implies \text{gcd}(y,x+y) = 1 \implies \text{gcd}(xy,x+y) = 1 \implies \text{gcd}(xy,x^2+xy+y^2) = 1 \implies\text{gcd}(x+y , x^2+xy+y^2) = 1$ and so $x^2+xy+y^2 \mid g \implies g \ge x^2+xy+y^2$
$g^3(x-y)^3 = g^2 \cdot g \cdot (x-y)^3 \ge g^2(x^2+y^2+xy) >g^2xy = ab$ $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

8864 posts

#23 h Dec 20, 2023, 10:56 PM

Y by

Let $a = dx$ and $b = dy$ where $d = \gcd(x, y)$ . Then it follows that $x^2+xy+y^2 \mid dxy(x+y).$ But as $\gcd(x^2+xy+y^2, xy(x+y)) = 1$ , it follows that $x^2+xy+y^2 \mid d$ . In particular, $|a-b|^3 \geq d^3 > d^2xy = ab$ as needed.

Z K Y

The post below has been deleted. Click to close.

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

427 posts

#24 h Jun 27, 2024, 11:26 PM • 1 Y

Y by deduck

Let $d:=\gcd(a,b)$ and $a=:md$ , $b:=nd$ . Then $m^2+mn+n^2\mid dmn(m+n)$ so $m^2+mn+n^2\mid dn^2$ . Since $m$ and $n$ are relatively prime, $m^2+mn+n^2$ and $n^2$ are relatively prime. Thus $m^2+mn+n^2\mid d$ so $d\geq m^2+mn+n^2>mn$ . Hence
$|a-b|=d|m-n|\geq d>\sqrt[3]{d^2mn}=\sqrt[3]{ab},$ as desired. $\square$

Z K Y

The post below has been deleted. Click to close.

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

139 posts

Ywgh1

#25 h Aug 21, 2024, 6:47 PM

Y by

Russia 2001

Let $\gcd(a,b)=d$ , and let $a=xd$ and $b=yd$ . We get that
$x^2+xy+y^2\mid dxy(x+y)$ Meaning that
$x^2+xy+y^2$
So we can easily get that $d\geq x^2+xy+y^2>xy$ .
Hence $|a-b|^3 \geq d^3 > d^2xy = ab$ .

This post has been edited 1 time. Last edited by Ywgh1, Aug 21, 2024, 6:55 PM

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

397 posts

alexanderhamilton124

#26 h Feb 6, 2025, 4:48 PM

Y by

$a^2 + ab + b^2 \mid ab^2 + a^2b - a^2b - ab^2 - b^3 \implies a^2 + ab + b^2 \mid b^3$ . We know $a^2 + ab + b^2 \mid a^3 - b^3$ , so $a^2 + ab + b^2 \mid a^3$ .

Hence, $v_p(a^2 + ab + b^2) \leq 3v_p(a), 3v_p(b)$ for all primes $p$ . Note that:
$v_p((a - b)^3) = 3v_p(a - b) \geq 3\min(v_p(a), v_p(b)) \geq v_p(a^2 + ab + b^2) \implies a^2 + ab + b^2 \mid (a - b)^3$ So, $a^2 + ab + b^2 \leq (a - b)^3 \implies \sqrt[3]{ab} < \sqrt[3]{a^2 + ab + b^2} \leq a - b$ , 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.

633 posts

#27 h Apr 26, 2025, 3:49 AM

Y by

From our condition, we have that $a^2 +ab + b^2 \mid a^2b + ab^2 + b^3 - (a^2b + ab^2) = b^3.$ Similarly, $a^2 + ab + b^2 \mid a^3.$ Hence, $a^2 + ab + b^2 \mid (a, b)^3 = (a, b - a)^3\mid (a - b)^3.$ Thus, $|b - a|^3 \geq a^2 + ab + b^2.$ AM-GM finishes.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a