IMO Team Selection Test 2, June 2020

First suppose that $a=1$. Then $\phi (1)=1$. For all positive integers $b$ we have $\gcd (a,b)=1$. Therefore in this case the equation is $1+b=1+\phi (b)+1$, or equivalently, $\phi (b)=b-1$. This is equivalent to the statement that there exists a unique integer from $\{1,2,\dots ,b\}$; which then has to be $b$ itself (since unless $b=1$, we have $\gcd (b,b)>1$, but if $b=1$ we have $\phi (b)=b$). In other words, this is equivalent to $b$ being a prime number. Hence the solutions for $a=1$ are precisely the pairs $(1,p)$ with $p$ a prime number. Similarly, the solutions for $b=1$ are precisely the pairs $(p,1)$ with $p$ a prime number.

Now assume that $a,b\ge 2$. As $\gcd (b,b)>1$ we have $\phi (b)\le b-1$. Therefore $$\gcd (a,b)=a+b-\phi (a)-\phi (b)\ge a-\phi (a)+1.$$ Let $p$ be the minimal prime divisor of $a$ (which exists as $a\ge 2$). Since for all multiples $tp\le a$ of $p$, we have $\gcd (tp,a)>1$, it follows that $a-\phi (a)\ge \frac{1}{p}\cdot a$. Therefore we have $$\gcd (a,b)\ge a-\phi (a)+1\ge \frac{a}{p}+1.$$ The two largest divisors of $a$ are $a$ and $\frac{a}{p}$. Since $\gcd (a,b)$ is a divisor of $a$ that is at least $\frac{a}{p}+1$, it must equal $a$. Hence $\gcd (a,b)=a$. In the same way we prove that $\gcd (a,b)=b$. So $a=b$.

The equation now is equivalent to $2a=2\phi (a)+a$, so also to $a=2\phi (a)$. Note that $2\mid a$. Therefore write $a=2^k\cdot m$ with $k\ge 1$ and $m$ odd. By a well-known property of the $\phi$-function, we have $\phi (a)=\phi (2^k)\cdot \phi (m)=2^{k-1}\cdot \phi (m)$, and the equation becomes $2^k\cdot m=2\cdot 2^{k-1}\cdot \phi (m)$, or equivalently $$m=\phi (m).$$ Therefore $m=1$, and $a=b=2^k$. Indeed, the equation holds for all pairs $(2^k,2^k)$ with $k\ge 1$.