Russian Math Olympiad Problem (2001) — Question and Answer

(Russia 2001).

Let a and b be distinct positive integers such that ab(a+b) is divisible by a^{2}+ab+b^{2}. Prove that

|a-b|> \sqrt[3]{ab}.

Proof.

Let g=gcd(a,b) and write a=xg and b=yg with gcd(x,y)=1. Then,

\frac{ab(a+b)}{a^{2}+ab+b^{2}}=\frac{xy(x+y)g}{x^{2}+xy+y^{2}}

is an integer. N^ote that gcd(x^{2}+xy+y^{2}, x)=gcd(y^{2},x)=1. Similarly, gcd(x^{2}+xy+y^{2},y)=1.

Because gcd(x+y,y)=1, we have

gcd(x^{2}+xy+y^{2},x+y)=gcd(y^{2}, x+y)=1

Now, we apply the following lemma: Let a and b be two coprime numbers. If c is an integer such that a|c, then ab|c.

Hence, we get, x^{2}+xy+y^{2}|g implying that g \geq x^{2}+xy+y^{2}. Therefore,

|a-b|^{3}=|g(x-y)|^{3}=g^{2}|x-y|^{3}.g \geq g^{2}.1.(x^{2}+xy+y^{2})>g^{2}xy=ab.

It follows that |a-b|>\sqrt[3]{ab}. QED.

Note that the key step x^{2}+xy+y^{2} divides g can also be obtained by clever algebraic manipulations such as a^{3}=(a^{2}+ab+b^{2})a-ab(a+b).

More Olympiad problems later,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s