Maths Olympiad Prep

Library / /13 of 41

, 2015

Number theory Difficulty 8.0 National Olympiad, round 2 Prove it Slovenia

Let a,b>1a, b > 1 be positive integers such that the number a+ba + b divides the number D(a,b)+v(a,b)D(a, b) + v(a, b). Here D(a,b)D(a, b) and v(a,b)v(a, b) denote the greatest common divisor and the least common multiple of the numbers aa and bb respectively. Prove that
D(a,b)+v(a,b)a+ba+b4. \frac{D(a,b) + v(a,b)}{a+b} \le \frac{a+b}{4}.

Solution

Let d=D(a,b)d = D(a, b). We can write a=a1da = a_1 d and b=b1db = b_1 d, where a1a_1 and b1b_1 are co-prime. We have v(a,b)=a1b1dv(a, b) = a_1 b_1 d. We insert this in the condition of the problem to get
a1d+b1dd+a1b1da1+b11+a1b1, a_1 d + b_1 d \mid d + a_1 b_1 d \Rightarrow a_1 + b_1 \mid 1 + a_1 b_1,
and we can rearrange the inequality to
d+a1b1da1d+b1da1d+b1d41+a1b1d(a1+b1)244d(a12+b12)+(2d4)a1b1. \frac{d + a_1 b_1 d}{a_1 d + b_1 d} \le \frac{a_1 d + b_1 d}{4} \Leftrightarrow 1 + a_1 b_1 \le d \frac{(a_1 + b_1)^2}{4} \Leftrightarrow 4 \le d(a_1^2 + b_1^2) + (2d - 4)a_1 b_1.
If d2d \ge 2 we have
d(a12+b12)+(2d4)a1b12(a12+b12)+(224)a1b1=2(a12+b12)2(12+12)=4, d(a_1^2 + b_1^2) + (2d - 4)a_1 b_1 \ge 2(a_1^2 + b_1^2) + (2 \cdot 2 - 4)a_1 b_1 = 2(a_1^2 + b_1^2) \ge 2(1^2 + 1^2) = 4,
Lets now check the case when d=1d = 1. We must prove the inequality
4a12+b122a1b14(a1b1)22a1b1. 4 \le a_1^2 + b_1^2 - 2a_1 b_1 \Leftrightarrow 4 \le (a_1 - b_1)^2 \Leftrightarrow 2 \le |a_1 - b_1|.
This means we have to prove that the numbers a1a_1 and b1b_1 differ by at least 2. Hence it suffices to check if that they do not differ for less.
If a1=b1a_1 = b_1 we get a1=b1=1a_1 = b_1 = 1 due to co-primality and hence a=b=1a = b = 1, which is impossible.

If the numbers differ by 1 we may assume that b1=a1+1b_1 = a_1 + 1 since the other case is symmetric. We insert this to the condition of the problem to get
a1+(a1+1)1+a1(a1+1)=a12+a1+12a1+12(a12+a1+1)=(2a1+1)a1+a1+22a1+1a1+2 \begin{align*} a_1 + (a_1 + 1) \mid 1 + a_1(a_1 + 1) & = a_1^2 + a_1 + 1 \\ \Rightarrow \quad 2a_1 + 1 \mid 2(a_1^2 + a_1 + 1) & = (2a_1 + 1)a_1 + a_1 + 2 \\ \Rightarrow \quad 2a_1 + 1 \mid a_1 + 2 \end{align*}
However, since 2a1+1a1+22a_1 + 1 \ge a_1 + 2 this is possible only if a1=1a_1 = 1. Since d=1d = 1 we again get a=1a = 1, which is impossible since a,b>1a, b > 1.
Thus we proved that the numbers a1a_1 and b1b_1 differ by at least 2 which proves the inequality.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.