The South African Mathematical Olympiad Third Round

(a) Suppose that $$ax+\gcd (a,x)+\text{lcm}(a,x)=ay+\gcd (a,y)+\text{lcm}(a,y)$$ for certain positive integers $a$, $x$, $y$. It follows that $$\gcd (a,ax+\gcd (a,x)+\text{lcm}(a,x))=\gcd (a,ay+\gcd (a,y)+\text{lcm}(a,y)).$$ Since $a$ divides both $ax$ and $\text{lcm}(a,x)$, we have $$\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)+\text{lcm}(a,y))=\gcd (a,\gcd (a,y))=\gcd (a,y).$$ Therefore, we must have $\gcd (a,x)=\gcd (a,y)=d$ for some positive integer $d$. Since $\text{lcm}(a,x)=ax/\gcd (a,x)$ and $\text{lcm}(a,y)=ay/\gcd (a,y)$, this gives us $$ax+d+\frac{ax}{d}=ay+d+\frac{ay}{d},$$ so $$ax\left(1+\frac{1}{d}\right)=ay\left(1+\frac{1}{d}\right),$$ which implies $x=y$. This proves the first statement.

(b) Suppose that $ax+\gcd (a,x)+\text{lcm}(a,x)=2014$. Note that the left hand side is divisible by $\gcd (a,x)$, so $\gcd (a,x)$ has to be a divisor of 2014, i.e., one of $1,2,19,38,53,106,1007,2014$. On the other hand, $$(\gcd (a,x)+1)(\text{lcm}(a,x)+1)=ax+\gcd (a,x)+\text{lcm}(a,x)+1=2015,$$ so $\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$. But then $ax+\text{lcm}(a,x)=0$, which is clearly impossible since the left hand side is positive.