49th International Mathematical Olympiad Spain

There is a unique solution: the function $f:\mathbb{N}\to \mathbb{N}$ defined by $f(1)=1$ and $$f(n)=p_1^{p_1^{a_1}-1}{p}_2^{p_2^{a_2}-1}\cdots p_k^{p_k^{a_k}-1}\text{ where }n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}\text{ is the prime factorization of }n>1.$$ Direct verification shows that this function meets the requirements.

Conversely, let $f:\mathbb{N}\to \mathbb{N}$ satisfy (i) and (ii). Applying (i) for $x=1$ gives $d(f(1))=1$, so $f(1)=1$. In the sequel we prove that (1) holds for all $n>1$. Notice that $f(m)=f(n)$ implies $m=n$ in view of (i). The formula $d\left(p_1^{b_1}\cdots p_k^{b_k}\right)=\left(b_1+1\right)\cdots \left(b_k+1\right)$ will be used throughout.

Let $p$ be a prime. Since $d(f(p))=p$, the formula just mentioned yields $f(p)=q^{p-1}$ for some prime $q$; in particular $f(2)=q^{2-1}=q$ is a prime. We prove that $f(p)=p^{p-1}$ for all primes $p$.

Suppose that $p$ is odd and $f(p)=q^{p-1}$ for a prime $q$. Applying (ii) first with $x=2$, $y=p$ and then with $x=p,y=2$ shows that $f(2p)$ divides both $(2-1)p^{2p-1}f(2)=p^{2p-1}f(2)$ and $(p-1)2^{2p-1}f(p)=(p-1)2^{2p-1}{q}^{p-1}$. If $q\ne p$ then the odd prime $p$ does not divide $(p-1)2^{2p-1}{q}^{p-1}$, hence the greatest common divisor of $p^{2p-1}f(2)$ and $(p-1)2^{2p-1}{q}^{p-1}$ is a divisor of $f(2)$. Thus $f(2p)$ divides $f(2)$ which is a prime. As $f(2p)>1$, we obtain $f(2p)=f(2)$ which is impossible. So $q=p$, i.e. $f(p)=p^{p-1}$.

For $p=2$ the same argument with $x=2,y=3$ and $x=3,y=2$ shows that $f(6)$ divides both $3^{5}f(2)$ and $2^{6}f(3)=2^6{3}^2$. If the prime $f(2)$ is odd then $f(6)$ divides $3^2=9$, so $f(6)\in \{1,3,9\}$. However then $6=d(f(6))\in \{d(1),d(3),d(9)\}=\{1,2,3\}$ which is false. In conclusion $f(2)=2$.

Next, for each $n>1$ the prime divisors of $f(n)$ are among the ones of $n$. Indeed, let $p$ be the least prime divisor of $n$. Apply (ii) with $x=p$ and $y=n/p$ to obtain that $f(n)$ divides $(p-1)y^{n-1}f(p)=(p-1)y^{n-1}{p}^{p-1}$. Write $f(n)=\ell P$ where $\ell$ is coprime to $n$ and $P$ is a product of primes dividing $n$. Since $\ell$ divides $(p-1)y^{n-1}{p}^{p-1}$ and is coprime to $y^{n-1}{p}^{p-1}$, it divides $p-1$; hence $d(\ell )\le \ell <p$. But (i) gives $n=d(f(n))=d(\ell P)$, and $d(\ell P)=d(\ell )d(P)$ as $\ell$ and $P$ are coprime. Therefore $d(\ell )$ is a divisor of $n$ less than $p$, meaning that $\ell =1$ and proving the claim.

Now (1) is immediate for prime powers. If $p$ is a prime and $a\ge 1$, by the above the only prime factor of $f\left(p^a\right)$ is $p$ (a prime factor does exist as $f\left(p^a\right)>1$). So $f\left(p^a\right)=p^b$ for some $b\ge 1$, and (i) yields $p^a=d\left(f\left(p^a\right)\right)=d\left(p^b\right)=b+1$. Hence $f\left(p^a\right)=p^{p^a-1}$, as needed.

Let us finally show that (1) is true for a general $n>1$ with prime factorization $n=p_1^{a_1}\cdots p_k^{a_k}$. We saw that the prime factorization of $f(n)$ has the form $f(n)=p_1^{b_1}\cdots p_k^{b_k}$. For $i=1,\dots ,k$, set $x=p_i^{a_i}$ and $y=n/x$ in (ii) to infer that $f(n)$ divides $\left(p_i^{a_i}-1\right)y^{n-1}f\left(p_i^{a_i}\right)$. Hence $p_i^{b_i}$ divides $\left(p_i^{a_i}-1\right)y^{n-1}f\left(p_i^{a_i}\right)$, and because $p_i^{b_i}$ is coprime to $\left(p_i^{a_i}-1\right)y^{n-1}$, it follows that $p_i^{b_i}$ divides $f\left(p_i^{a_i}\right)=p_i^{p_i^{a_i}-1}$. So $b_i\le p_i^{a_i}-1$ for all $i=1,\dots ,k$. Combined with (i), these conclusions imply $$p_1^{a_1}\cdots p_k^{a_k}=n=d(f(n))=d\left(p_1^{b_1}\cdots p_k^{b_k}\right)=\left(b_1+1\right)\cdots \left(b_k+1\right)\le p_1^{a_1}\cdots p_k^{a_k}$$ Hence all inequalities $b_i\le p_i^{a_i}-1$ must be equalities, $i=1,\dots ,k$, implying that (1) holds true. The proof is complete.