Problem

Source: ELMO 2020 P6

Tags: number theory



For any positive integer $n$, let $\tau(n)$ denote the number of positive integer divisors of $n$, $\sigma(n)$ denote the sum of the positive integer divisors of $n$, and $\varphi(n)$ denote the number of positive integers less than or equal to $n$ that are relatively prime to $n$. Let $a,b > 1$ be integers. Brandon has a calculator with three buttons that replace the integer $n$ currently displayed with $\tau(n)$, $\sigma(n)$, or $\varphi(n)$, respectively. Prove that if the calculator currently displays $a$, then Brandon can make the calculator display $b$ after a finite (possibly empty) sequence of button presses. Proposed by Jaedon Whyte.