Task 2. Given is the function $f: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}$ that satisfies the properties:

(i) $f(p)=1$ for all prime numbers $p$,

(ii) $f(x y)=y f(x)+x f(y)$ for all $x, y \in \mathbb{Z}_{>0}$.

Determine the smallest $n \geq 2016$ with $f(n)=n$.
Solution. We first prove that for prime numbers $p$ and positive integers $k$, it holds that $f\left(p^{k}\right)=k p^{k-1}$. We do this by induction on $k$. For $k=1$, we have $f(p)=1$ and this is given. Now let $l \geq 1$ and assume we have proven it for $k=l$. Consider $k=l+1$. Then we apply the second property with $x=p$ and $y=p^{l}$:

$$
f\left(p^{l+1}\right)=f\left(p \cdot p^{l}\right)=p^{l} \cdot f(p)+p \cdot f\left(p^{l}\right)=p^{l}+p \cdot l p^{l-1}=(l+1) p^{l}.
$$

This completes the induction. Now we prove that for different prime numbers $p_{1}, p_{2}, \ldots$, $p_{t}$ and positive integers $a_{1}, a_{2}, \ldots, a_{t}$, it holds that

$$
f\left(p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{t}^{a_{t}}\right)=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{t}^{a_{t}} \cdot\left(\frac{a_{1}}{p_{1}}+\frac{a_{2}}{p_{2}}+\cdots+\frac{a_{t}}{p_{t}}\right)
$$

We prove this by induction on $t$. For $t=1$, it is exactly the formula we proved earlier. Now let $r \geq 1$ and assume we have proven it for $t=r$. Then we apply the second property again:

$$
\begin{aligned}
f\left(p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} \cdot p_{r+1}^{a_{r+1}}\right) & =p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} \cdot f\left(p_{r+1}^{a_{r+1}}\right)+p_{r+1}^{a_{r+1}} \cdot f\left(p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}}\right) \\
& =p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} \cdot a_{r+1} p_{r+1}^{a_{r+1}-1}+p_{r+1}^{a_{r+1}} \cdot p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} \cdot\left(\frac{a_{1}}{p_{1}}+\frac{a_{2}}{p_{2}}+\cdots+\frac{a_{r}}{p_{r}}\right) \\
& =p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} p_{r+1}^{a_{r+1}} \cdot \frac{a_{r+1}}{p_{r+1}}+p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} p_{r+1}^{a_{r+1}} \cdot\left(\frac{a_{1}}{p_{1}}+\frac{a_{2}}{p_{2}}+\cdots+\frac{a_{r}}{p_{r}}\right) \\
& =p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{r}^{a_{r}} p_{r+1}^{a_{r+1}} \cdot\left(\frac{a_{1}}{p_{1}}+\frac{a_{2}}{p_{2}}+\cdots+\frac{a_{r}}{p_{r}}+\frac{a_{r+1}}{p_{r+1}}\right).
\end{aligned}
$$

This completes the induction.

For an integer $n>1$ of the form $n=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{t}^{a_{t}}$ with the $p_{i}$ different prime numbers, the property $f(n)=n$ is equivalent to

$$
p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{t}^{a_{t}} \cdot\left(\frac{a_{1}}{p_{1}}+\frac{a_{2}}{p_{2}}+\cdots+\frac{a_{t}}{p_{t}}\right)=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{t}^{a_{t}}
$$

or equivalently,

$$
\frac{a_{1}}{p_{1}}+\frac{a_{2}}{p_{2}}+\cdots+\frac{a_{t}}{p_{t}}=1
$$

Multiplying by $p_{1} p_{2} \cdots p_{t}$ gives

$$
a_{1} p_{2} p_{3} \cdots p_{t}+a_{2} p_{1} p_{3} \cdots p_{t}+\ldots+a_{t} p_{1} p_{2} \cdots p_{t-1}=p_{1} p_{2} \cdots p_{t}
$$

Assume without loss of generality that $p_{1}$ is the smallest prime number that occurs in the prime factorization of $n$. In the expression above, $p_{1}$ is a divisor of the right-hand side and of every term on the left-hand side except possibly the first. But then $p_{1}$ must also be a divisor of the first term. Since $p_{2}, \ldots, p_{t}$ are all prime numbers different from $p_{1}$, this can only be if $p_{1} \mid a_{1}$. In particular, then $a_{1} \geq p_{1}$, so $\frac{a_{1}}{p_{1}} \geq 1$. We now see that equality must hold and that $t=1$, because otherwise the sum of all $\frac{a_{i}}{p_{i}}$ would be greater than 1. Thus, $n=p^{p}$ for some prime number $p$.

We are looking for the smallest $n \geq 2016$ of the form $n=p^{p}$. We have $3^{3}=27$ and $5^{5}=3125$, so the desired $n$ is equal to 3125.