Maths Olympiad Prep

Library / /5 of 22

Number theory Difficulty 5.7 AIME, harder Prove it South Africa

(a) Let aa, xx, yy be positive integers. Prove: if xyx \neq y, then also
ax+gcd(a,x)+lcm(a,x)ay+gcd(a,y)+lcm(a,y). ax + \gcd(a, x) + \text{lcm}(a, x) \neq ay + \gcd(a, y) + \text{lcm}(a, y).
(b) Show that there are no two positive integers aa and bb such that
ab+gcd(a,b)+lcm(a,b)=2014. ab + \gcd(a, b) + \text{lcm}(a, b) = 2014.

Solution

(a) Suppose that
ax+gcd(a,x)+lcm(a,x)=ay+gcd(a,y)+lcm(a,y) ax + \gcd(a, x) + \text{lcm}(a, x) = ay + \gcd(a, y) + \text{lcm}(a, y)
for certain positive integers aa, xx, yy. It follows that
gcd(a,ax+gcd(a,x)+lcm(a,x))=gcd(a,ay+gcd(a,y)+lcm(a,y)). \gcd(a, ax + \gcd(a, x) + \text{lcm}(a, x)) = \gcd(a, ay + \gcd(a, y) + \text{lcm}(a, y)).
Since aa divides both axax and lcm(a,x)\text{lcm}(a, x), we have
gcd(a,ax+gcd(a,x)+lcm(a,x))=gcd(a,gcd(a,x))=gcd(a,x) \gcd(a, ax + \gcd(a, x) + \text{lcm}(a, x)) = \gcd(a, \gcd(a, x)) = \gcd(a, x)
and likewise
gcd(a,ay+gcd(a,y)+lcm(a,y))=gcd(a,gcd(a,y))=gcd(a,y). \gcd(a, ay + \gcd(a, y) + \text{lcm}(a, y)) = \gcd(a, \gcd(a, y)) = \gcd(a, y).
Therefore, we must have gcd(a,x)=gcd(a,y)=d\gcd(a, x) = \gcd(a, y) = d for some positive integer dd. Since lcm(a,x)=ax/gcd(a,x)\text{lcm}(a, x) = ax/\gcd(a, x) and lcm(a,y)=ay/gcd(a,y)\text{lcm}(a, y) = ay/\gcd(a, y), this gives us
ax+d+axd=ay+d+ayd, ax + d + \frac{ax}{d} = ay + d + \frac{ay}{d},
so
ax(1+1d)=ay(1+1d), ax \left(1 + \frac{1}{d}\right) = ay \left(1 + \frac{1}{d}\right),
which implies x=yx = y. This proves the first statement.

(b) Suppose that ax+gcd(a,x)+\lcm(a,x)=2014ax+\gcd(a,x)+\lcm(a,x) = 2014. Note that the left hand side is divisible by gcd(a,x)\gcd(a,x), so gcd(a,x)\gcd(a,x) has to be a divisor of 2014, i.e., one of 1,2,19,38,53,106,1007,20141, 2, 19, 38, 53, 106, 1007, 2014. On the other hand,
(gcd(a,x)+1)(\lcm(a,x)+1)=ax+gcd(a,x)+\lcm(a,x)+1=2015, (\gcd(a, x) + 1)(\lcm(a, x) + 1) = ax + \gcd(a, x) + \lcm(a, x) + 1 = 2015,
so gcd(a,x)+1\gcd(a, x) + 1 has to divide 2015. Since 2, 3, 20, 39, 54, 107, 1008 are all not divisors of 2015, this leaves us with gcd(a,x)=2014\gcd(a, x) = 2014. But then ax+\lcm(a,x)=0ax + \lcm(a, x) = 0, which is clearly impossible since the left hand side is positive.

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.