Maths Olympiad Prep

Library / /84 of 121

Number theory Difficulty 6.5 National Olympiad Prove it India

Problem:

Let aa, bb be natural numbers with ab>2a b > 2. Suppose that the sum of their greatest common divisor and least common multiple is divisible by a+ba + b. Prove that the quotient is at most (a+b)/4(a + b) / 4. When is this quotient exactly equal to (a+b)/4(a + b) / 4?

Solution

Solution:

Let gg and ll denote the greatest common divisor and the least common multiple, respectively, of aa and bb. Then gl=abg l = a b. Therefore g+lab+1g + l \leq a b + 1.

Suppose that (g+l)/(a+b)>(a+b)/4(g + l) / (a + b) > (a + b) / 4. Then we have ab+1>(a+b)2/4a b + 1 > (a + b)^2 / 4, so we get (ab)2<4(a - b)^2 < 4.

Assuming aba \geq b we either have a=ba = b or a=b+1a = b + 1.

In the former case, g=l=ag = l = a and the quotient is (g+l)/(a+b)=1(a+b)/4(g + l) / (a + b) = 1 \leq (a + b) / 4.

In the latter case, g=1g = 1 and l=b(b+1)l = b(b + 1) so we get that 2b+12b + 1 divides b2+b+1b^2 + b + 1. Therefore 2b+12b + 1 divides 4(b2+b+1)(2b+1)2=34(b^2 + b + 1) - (2b + 1)^2 = 3 which implies that b=1b = 1 and a=2a = 2, a contradiction to the given assumption that ab>2a b > 2.

This shows that (g+l)/(a+b)(a+b)/4(g + l) / (a + b) \leq (a + b) / 4.

Note that for the equality to hold, we need that either a=b=2a = b = 2 or, (ab)2=4(a - b)^2 = 4 and g=1g = 1, l=abl = a b. The latter case happens if and only if aa and bb are two consecutive odd numbers. (If a=2k+1a = 2k + 1 and b=2k1b = 2k - 1 then a+b=4ka + b = 4k divides ab+1=4k2a b + 1 = 4k^2 and the quotient is precisely (a+b)/4(a + b) / 4.)

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.