Russian Math Olympiad Problem (2001) — Question and Answer

Posted by nkpithwa

(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 Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

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

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

Connecting to %s

%d bloggers like this: