CMO 2017

Let $d(n)=f(f(n))$ denote the number of divisors of $n$ and observe that $f(d(n))=f(f(f(n)))=d(f(n))$ for all $n$. Also note that because all divisors of $n$ are distinct positive integers between $1$ and $n$, including $1$ and $n$, and excluding $n-1$ if $n>2$, it follows that $2\le d(n)<n$ for all $n>2$. Furthermore $d(1)=1$ and $d(2)=2$.

We first will show that $f(2)=2$. Let $m=f(2)$ and note that $2=d(2)=f(f(2))=f(m)$. If $m\ge 2$, then let $m_0$ be the smallest positive integer satisfying that $m_0\ge 2$ and $f(m_0)=2$. It follows that $f(d(m_0))=d(f(m_0))=d(2)=2$. By the minimality of $m_0$, it follows that $d(m_0)\ge m_0$, which implies that $m_0=2$. Therefore if $m\ge 2$, it follows that $f(2)=2$. It suffices to examine the case in which $f(2)=m=1$. If $m=1$, then $f(1)=f(f(2))=2$ and furthermore, each prime $p$ satisfies that $d(f(p))=f(d(p))=f(2)=1$ which implies that $f(p)=1$. Therefore $d(f(p^2))=f(d(p^2))=f(3)=1$ which implies that $f(p^2)=1$ for any prime $p$. This implies that $3=d(p^2)=f(f(p^2))=f(1)=2$, which is a contradiction. Therefore $m\ne 1$ and $f(2)=2$.

It now follows that if $p$ is prime then $2=f(2)=f(d(p))=d(f(p))$ which implies that $f(p)$ is prime. $\square$