Maths Olympiad Prep

Library / /30 of 86

Number theory Difficulty 5.6 AIME, harder Prove it Estonia

Find all pairs (a,b)(a, b) of positive integers such that aba \ge b and
1a+1b=12021. \frac{1}{a} + \frac{1}{b} = \frac{1}{2021}.

Solution

Solution 1: Let d=gcd(a,b)d = \gcd(a,b), a=daa = da', b=dbb = db'. The given equation reduces to 1da+1db=12021\frac{1}{da'} + \frac{1}{db'} = \frac{1}{2021} which is equivalent to
2021(a+b)=dab.(4) 2021(a' + b') = da'b'. \qquad (4)
As aa' and bb' are relatively prime to each other, they both are relatively prime to a+ba' + b', implying that aba'b' and a+ba' + b' are relatively prime. By (4), ab2021(a+b)a'b' \mid 2021(a' + b'), implying ab2021a'b' \mid 2021. As 2021=43472021 = 43 \cdot 47 where the factors are prime, the number 20212021 has exactly four positive factors 11, 4343, 4747 and 20212021. Taking into account that aba \ge b holds if and only if aba' \ge b', consider all cases:
* If a=2021a' = 2021 and b=1b' = 1 then (4) implies d=2022d = 2022. Consequently, (a,b)=(20212022,2022)(a,b) = (2021 \cdot 2022, 2022).
* If a=47a' = 47 and b=43b' = 43 then (4) implies d=90d = 90. Consequently, (a,b)=(4790,4390)(a,b) = (47 \cdot 90, 43 \cdot 90).
* If a=47a' = 47 and b=1b' = 1 then (4) implies d=4348d = 43 \cdot 48. Consequently, (a,b)=(202148,4348)(a,b) = (2021 \cdot 48, 43 \cdot 48).
* If a=43a' = 43 and b=1b' = 1 then (4) implies d=4744d = 47 \cdot 44. Consequently, (a,b)=(202144,4744)(a,b) = (2021 \cdot 44, 47 \cdot 44).
* If a=1a' = 1 and b=1b' = 1 then (4) implies d=20212d = 2021 \cdot 2. Thus (a,b)=(20212,20212)(a,b) = (2021 \cdot 2, 2021 \cdot 2).

Solution 2: The given equation is equivalent to a+bab=12021\frac{a+b}{ab} = \frac{1}{2021} which reduces to ab2021a2021b=0ab - 2021a - 2021b = 0. After adding 202122021^2 to both sides and factorizing in the l.h.s, we get
(a2021)(b2021)=20212.(5) (a - 2021)(b - 2021) = 2021^2. \qquad (5)
As both aa and bb are positive, the factors in the l.h.s. of (5) are greater than 2021-2021. Thus if both factors were negative then the absolute value of their product would be less than 202122021^2 and (5) could not hold. Hence both factors are positive. Since aba \ge b, we must have a2021b2021a - 2021 \ge b - 2021. As 2021=43472021 = 43 \cdot 47 with factors being prime, we obtain variants (a2021,b2021)=(20212,1)(a - 2021, b - 2021) = (2021^2, 1), (a2021,b2021)=(202147,43)(a - 2021, b - 2021) = (2021 \cdot 47, 43), (a2021,b2021)=(202143,47)(a - 2021, b - 2021) = (2021 \cdot 43, 47), (a2021,b2021)=(472,432)(a - 2021, b - 2021) = (47^2, 43^2) and (a2021,b2021)=(2021,2021)(a - 2021, b - 2021) = (2021, 2021). Consequently, (a,b)=(20212022,2022)(a,b) = (2021 \cdot 2022, 2022), (a,b)=(202148,4348)(a,b) = (2021 \cdot 48, 43 \cdot 48), (a,b)=(202144,4744)(a,b) = (2021 \cdot 44, 47 \cdot 44), (a,b)=(4790,4390)(a,b) = (47 \cdot 90, 43 \cdot 90), or (a,b)=(20212,20212)(a,b) = (2021 \cdot 2, 2021 \cdot 2).

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 and solution reproduced as published; topic and difficulty added by this site.