Maths Olympiad Prep

Library / /21 of 39

Number theory Difficulty 5.4 AIME, harder Prove it Ireland

Let aa, bb, nn be positive integers such that
1a+1b+nlcm(a,b)=1gcd(a,b) \frac{1}{a} + \frac{1}{b} + \frac{n}{\text{lcm}(a, b)} = \frac{1}{\gcd(a, b)}
(i) Prove that nn is odd;
(ii) Find all the possible values of aa and bb if n=2007n = 2007.

Solution

(i) Let d=gcd(a,b)d = \gcd(a, b). There exist two positive integers xx and yy which are relatively prime such that a=dxa = dx, b=dyb = dy. Using this fact in the initial equality we find x+y+n=xyx + y + n = xy, that is, (x1)(y1)=n+1(x - 1)(y - 1) = n + 1. Since xx and yy are relatively prime numbers, at least one of them is odd. Then (x1)(y1)(x - 1)(y - 1) is even, so nn is odd.

(ii) As before, we are led to the equation (x1)(y1)=2008=23251(x - 1)(y - 1) = 2008 = 2^3 \cdot 251. Since xx and yy are relatively prime, the possibilities for (x,y)(x, y) are (2,2009)(2, 2009), (9,252)(9, 252), (252,9)(252, 9), (2009,2)(2009, 2). The complete set of solutions (a,b)(a, b) is

\{(2d, 2009d), (9d, 252d), (252d, 9d), (2009d, 2d) : d \ge 1\}.

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.