Everyone who has spent a few hours(minutes) thinking about the problem would have figured out that $ f(1) = 1, f(p^a) = p^{p^a - 1}$ where $ p$ is a prime number. In any case I'll prove these two facts at the end. Using the above two facts and the conditions given in the problem, we will prove that $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = f(p_1^{a_1})f(p_2^{a_2})...f(p_k^{a_k})$ where $ p_i$ is prime for $ 1 \leq i \leq k$ We write $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = f(p_1\cdot p_1^{a_1 - 1}p_2^{a_2}...p_k^{a_k})$ Using the second condition given in the problem,(i.e) $ f(xy)$ divides $ (x - 1)y^{xy - 1}f(x) \;\; \forall x, y\in\mathbb{N}$, we get the following $ f(p_1\cdot p_1^{a_1 - 1}p_2^{a_2}...p_k^{a_k})\;|\; (p_1 - 1)(p_1^{a_1 - 1}p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} - 1}f(p_1)$ $ \Rightarrow f(p_1\cdot p_1^{a_1 - 1}p_2^{a_2}...p_k^{a_k})\;|\; (p_1 - 1)(p_1^{a_1 - 1}p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} - 1}p_1^{p_1 - 1}$ (using $ f(p_1) = p_1^{p_1 - 1}$). We repeat this for every $ p_i$ and we get that $ \forall i\in \mathbb{N}$ such that $ 1\leq i \leq k$, $ f(p_i\cdot p_1^{a_1}p_2^{a_2}...p_i^{a_i - 1}...p_k^{a_k})\;|\; (p_i - 1)(p_1^{a_1}p_2^{a_2}...p_i^{a_i - 1}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} - 1}p_i^{p_i - 1}$ The above observations imply that $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = q_1^{c_1}q_2^{c_2}...q_m^{c_m}\cdot p_1^{x_1}p_2^{x_2}...p_k^{x_k}$ where $ q_i$ is prime for $ 1 \leq i \leq m$ and $ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p_i - 1) \;\;\forall i \in \mathbb{N}$, such that $ 1\leq i \leq k$. We note that the number of divisors of $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})$ is $ (c_1 + 1)(c_2 + 1)...(c_m + 1)(x_1 + 1)(x_2 + 1)...(x_k + 1)$. The number of divisors of $ f(x)$, $ d\left(f(x)\right) = x \;\;\forall x\in\mathbb{N}$. This when applied to $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})$, gives us the following equation $ p_1^{a_1}p_2^{a_2}...p_k^{a_k} = (c_1 + 1)(c_2 + 1)...(c_m + 1)(x_1 + 1)(x_2 + 1)...(x_k + 1)$ Since $ (c_1 + 1)\;|\;p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, there exists an $ i$ such that $ c_1 \equiv - 1 (mod \;p_i) \Rightarrow c_1 \geq p_i - 1 \Rightarrow q_1^{c_1} \geq q_1^{p_i - 1} \geq 2^{p_i - 1} > p_i - 1$. We know that $ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p_i - 1) \Rightarrow q_1^{c_1}q_2^{c_2}...q_m^{c_m} \leq p_i - 1 \Rightarrow q_1^{c_1} \leq p_i - 1$. But we established above that $ q_1^{c_1} > p_i - 1$. Hence, our assumption that $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = q_1^{c_1}q_2^{c_2}...q_m^{c_m}\cdot p_1^{x_1}p_2^{x_2}...p_k^{x_k}$ is incorrect. Therefore, $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = p_1^{x_1}p_2^{x_2}...p_k^{x_k}$ We would again have to use condition (ii) from the problem. This time we write $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})$ Using condition (ii), we get the following $ f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})\;|\; (p_1^{a_1 - 1} - 1)(p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} - 1}f(p_1^{a_1})$ $ \Rightarrow f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})\;|\; (p_1^{a_1} - 1)(p_2^{a_2}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} - 1}p_1^{p_1^{a_1} - 1}$ (using $ f(p_1^{a_1}) = p_1^{p_1^{a_1} - 1}$). $ \Rightarrow$ the power of $ p_1$ in $ f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})$ is $ x_1 \leq p_1^{a_1} - 1$ We repeat this for every $ p_i$ and we get that $ \forall i\in \mathbb{N}$ such that $ 1\leq i \leq k$, $ f(p_i^{a_i}\cdot p_1^{a_1}...p_{i - 1}^{a_{i - 1}}p_{i + 1}^{a_{i + 1}}...p_k^{a_k})\;|\; (p_i^{a_i} - 1)(p_1^{a_1}...p_{i - 1}^{a_{i - 1}}p_{i + 1}^{a_{i + 1}}...p_k^{a_k})^{p_1^{a_1}p_2^{a_2}...p_k^{a_k} - 1}p_i^{p_i^{a_i} - 1}$ $ \Rightarrow$ the power of $ p_i$ in $ f(p_1^{a_1}\cdot p_2^{a_2}...p_k^{a_k})$ is $ x_i \leq p_i^{a_i} - 1$ The above observations imply that $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = p_1^{x_1}p_2^{x_2}...p_k^{x_k}$ where $ x_i \leq p_i^{a_i} - 1$ for $ 1 \leq i \leq k$. From condition(i) in the problem, we have that $ p_1^{a_1}p_2^{a_2}...p_k^{a_k} = (x_1 + 1)(x_2 + 1)...(x_k + 1) \leq p_1^{a_1}p_2^{a_2}...p_k^{a_k}\;\; (\because x_i \leq p_i^{a_i} - 1)$. Hence, $ x_i = p_i^{a_i} - 1\;\; \forall i \in \mathbb{N}$ such that $ 1\leq i \leq k$. Therefore, $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = f(p_1^{a_1})f(p_2^{a_2})...f(p_k^{a_k})$ where $ p_i$ is prime for $ 1 \leq i \leq k$ Now it remains to show that (i) $ f(1) = 1$ and (ii) $ f(p^a) = p^{p^a - 1}$. Since $ d(f(1)) = 1$, we have $ f(1) = 1$. We establish $ f(p^a) = p^{p^a - 1}$, by proving the following (a) $ f(2) = 2$ (b) $ f(p) = p^{p - 1}$ for all odd prime $ p$ (c) for $ a \geq 2$, $ f(p^a)$ has to be a power of $ p$ (i.e.) $ f(p^a) = p^{x}$. Statement (c) along with $ d(f(p^a)) = p^a \Rightarrow x + 1 = p^{a} \Rightarrow x = p^{a} - 1 \Rightarrow f(p^a) = p^{p^{a} - 1}$. Hence, it is enough to establish (a),(b) and (c). Proof of (a): As $ d(f(2)) = 2$, $ f(2) = p$ where $ p$ is a prime. Suppose $ p$ is an odd prime. $ f(2\cdot p)\; |\; p^{2p - 1}f(2) = p^{2p} \Rightarrow f(2p) = p^{y}$ Since $ d(f(2p)) = 2p$, we have $ f(2p) = p^{2p - 1}$. $ f(p\cdot 2)\; |\; (p - 1) 2^{2p - 1}f(p) \Rightarrow p^{2p - 1}\;|\; (p - 1) 2^{2p - 1}f(p) \Rightarrow p^{2p - 1}\;|\; f(p) \Rightarrow f(p) = p^{z}$ where $ z \geq 2p - 1$. This implies $ d(f(p)) \geq 2p$. But $ d(f(p)) = p$ This is a contradiction. Hence, $ f(2)$ cannot be an odd prime. Therefore, $ f(2) = 2$. Proof of (b): Suppose $ p$ is an odd prime. Since $ d(f(p)) = p$, $ f(p) = q^{p - 1}$ for some prime $ q$. In other words, $ f(p)$ has exactly one prime factor. Now if we could show that $ p \;|\; f(p)$, then it would follow that $ f(p) = p^{p - 1}$. $ f(2\cdot p)\; |\; p^{2p - 1}f(2) = 2p^{2p - 1} \Rightarrow f(2p) = 2^{x}p^{y}$ where $ x \leq 1, y \geq 0$. Since $ d(f(2p)) = 2p$, we have $ (x + 1)(y + 1) = 2p \Rightarrow y \geq p - 1$. $ f(p\cdot 2)\; |\; (p - 1) 2^{2p - 1}f(p) \Rightarrow 2^{x}p^{y}\;|\; (p - 1) 2^{2p - 1}f(p) \Rightarrow p^{y}\;|\; f(p) \Rightarrow f(p) = p^{p - 1}$. Proof of (c): Let $ k \geq 1$ We write $ f(p^{k + 1}) = f(p\cdot p^{k}) \; |\; (p - 1)(p^k)^{(p^{k + 1} - 1)}f(p) = (p - 1)(p^k)^{(p^{k + 1} - 1)}p^{p - 1}$ $ \Rightarrow f(p^{k + 1}) = q_1^{c_1}q_2^{c_2}..q_m^{c_m}p^{x}$ where $ q_i$ is prime for $ 1 \leq i \leq m$ and $ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p - 1)$. We note that the number of divisors of $ f(p^{k + 1})$ is $ (c_1 + 1)(c_2 + 1)...(c_m + 1)(x + 1)$. The number of divisors of $ f(x)$, $ d\left(f(x)\right) = x \;\;\forall x\in\mathbb{N}$. This when applied to $ f(p^{k + 1})$, gives us the following equation $ p^{k + 1} = (c_1 + 1)(c_2 + 1)...(c_m + 1)(x + 1)$ Since $ (c_1 + 1)\;|\;p^{k + 1}$, $ c_1 \equiv - 1 (mod \;p) \Rightarrow c_1 \geq p - 1 \Rightarrow q_1^{c_1} \geq q_1^{p - 1} \geq 2^{p - 1} > p - 1$. We know that $ q_1^{c_1}q_2^{c_2}...q_m^{c_m} \;|\; (p - 1) \Rightarrow q_1^{c_1}q_2^{c_2}...q_m^{c_m} \leq p - 1 \Rightarrow q_1^{c_1} \leq p - 1$. But we established above that $ q_1^{c_1} > p - 1$. Hence, our assumption that $ f(p^{k + 1}) = q_1^{c_1}q_2^{c_2}...q_m^{c_m} p^{x}$ is incorrect. Therefore, $ f(p^{k + 1}) = p^{x}$. We have proven (a),(b) and (c). Hence, $ f(p^a) = p^{p^a - 1}$. Therefore, the function that satisfies the conditions in the problem is the following: (i)$ f(1) = 1$,(ii) $ f(p^{a}) = p^{p^a - 1 }$ and (iii) $ f(p_1^{a_1}p_2^{a_2}...p_k^{a_k}) = f(p_1^{a_1})f(p_2^{a_2})...f(p_k^{a_k})$ where $ p_i$ is prime for $ 1 \leq i \leq k$.

Step 1:$ f(1)=1,f(2^a)=2^{2^a-1}$ Step 2:$ f(2p^a)=2p^{p^a-1},f(p^a)=p^{p^a-1}$ Step 3:the set of prime divisors of $ f(x)$ are containted in the set of prime divisors in $ x$ Step 4:$ f(p_1^{a_1}...p_k^{a_k})=p_1^{p^{a_1}-1}...p_k^{p^{a_k}-1}$ And I will post the full solution below(very sorry for being written in Chinese,I am glad to explain if anyone has questions)

I am grateful if anyone can point out my mistakes or flaws

Hi Hxy09, I was reading through your solution and realized that our solutions are very similar. On page 2 of your solution after the proof of $ f(p^{\alpha}) = p^{p^{\alpha}-1}$, I couldn't follow the arguments as you had written something in Chinese. Could you translate your solution into english from that point onwards till "....$ \exists \alpha \in \mathbb{N}_0 s.t. f(x) | x^{\alpha} \therefore (f(x),x-1) = 1$".

nicetry007 wrote: Hi Hxy09, I was reading through your solution and realized that our solutions are very similar. On page 2 of your solution after the proof of $ f(p^{\alpha}) = p^{p^{\alpha} - 1}$, I couldn't follow the arguments as you had written something in Chinese. Could you translate your solution into english from that point onwards till "....$ \exists \alpha \in \mathbb{N}_0 s.t. f(x) | x^{\alpha} \therefore (f(x),x - 1) = 1$". Ok,here we go: In page 2,we proved the set of prime divisors of $ f(x)$ are containted in the set of prime divisors of $ x$ ...(*) Firstly we pick out the smallest prime divisor of $ x$.and replaced $ x$ with $ py$(it doesn't matter whether $ y$ is coprime with $ p$) Noticed that $ f(p)=p^{p-1}$ $ f(py)|(p-1)y^{py-1}p^{p-1}$ If (*) is not true,denote by $ q$ $ q^ \beta ||f(py)$ and $ gcd(q,py)=1$ $ \beta \ge 1$ implies that $ q^{\beta}|p-1$,but $ d(f(py))=py$,$ \beta +1|py$ $ p$ is the smallest prime divisor of $ x$ So $ \beta +1 \ge p$ Then $ p-1 \ge q^{\beta} \ge q^{p-1} \ge 2^{p-1}$ This is absurd! Then the conclusion is true Very sorry for some typoes in the picture(directly from my notebook)

Hi Hxy09 Thanks for clarifying it. I sort of guessed that you had assumed $ p$ to be the smallest prime or something of that sort. It turns out my guess was right!!

First of all $d(f(1))=1 \implies f(1)=1$ Claim 1:$f(p)=p^{p-1}$ for all primes $p$. Proof:Let $p \ge 5$.Note that the condition $d(f(p))=p$ forces us to conclude that $f(p)$ has only one prime with power $p-1$,say $f(p)=q^{p-1}$.Let $f(3)=y^2$.Then taking $x=3,y=p$ we get $f(3p)|2p^{3p-1}f(3)=2p^{3p-1}y^2$ Also note that $f(3p)$ can have two forms:$r^2s^{p-1}$ or $r^{3p-1}$ where $r$ and $s$ are primes.In the former case $r=y,s=p$ and in the later case $r=p$ (This can be determined by checking the size of the exponents)..Taking $x=p,y=3$ we have $f(3p)|(p-1)3^{3p-1}f(p)=(p-1)3^{3p-1}q^{p-1}$.In the later case we have $f(3p)=p^{3p-1}$.Note that $p$ cannot be $3$ and cannot divide $p-1$ and the exponent $3p-1$ of $p$ is also greater than the exponent $p-1$ of $q$.So the later case cannot hold. Now consider the former case.In this case $f(3p)=y^2p^{p-1}$.Now $p$ cannot divide $p-1$ and $3$ so $p=q$.That is $f(p)=p^{p-1}$.Also we get $y^2|(p-1)3^{3p-1}$.This holds for arbitrary $p$ so choose $p$ such that $\text{gcd}(y^2,p-1)=1$.Then we get $y=3$ so $f(3)=3^2$ Now taking $x=2,y=3$ we get $f(6)|3^5f(2)$ Now using property (a) we get that $f(6)$ can have two forms namely,$lm^2$ or $l^5$ where $l,m$ are primes.In the first case we are forced to conclude that $m=3,l=f(2)$.In the second case we get $l=3$.Now taking $x=3,y=2$ and using $f(3)=3^2$ we get $f(6)|2^63^2$.So the second case cannot hold.The first case has to hold,hence $f(2)$ has to be $2$(in combination with property(a)).Now we are done with our claim. Claim 2:$f(p^{\alpha})=p^{{p^{\alpha}}-1} \forall \alpha \ge 1$ Proof:Taking $x=p,y=p^{n-1}$ we get $f(p^n)|(p-1)p^{(n-1)(p^n-1)+p-1}$.Now let the prime factorization of $f(p^n)$ be $\prod_{i=1}^{s}{{r_i}^{m_i}}$.Now $s \ge 2$ implies that ${r_k}^{m_k}|p-1$ for some $k$.Let $p-1={r_k}^{m_k}j$.Note that property (a) shows that $\prod_{i=1}^{s}{(m_i+1)}=p^n$ so $m_k$ must be of form $p^c-1$.In other words $p-1|m_k$.Taking modulo $p$ we get $-1 \equiv j \pmod{p}$ so $j$ must be atleast $p-1$,i.e., $r_k$ can atmost be $1$,a contradiction.Hence $s=1$ and combining this with property (a),we get $f(p^n)=p^{p^n-1}$.Claim 2 is established. Take $x=p_i,y={p_i}^{a_i-1}\prod_{j \neq i}{{p_j}^{a_j}}$.Then we get $f(\prod_{i=1}^{k}{{p_i}^{a_i}}|({p_i}-1)({p_i}^{a_i-1}\prod_{j \neq i}{{p_j}^{a_j}})^{\prod_{i=1}^{k}{{p_i}^{a_i}}-1}{p_i}^{p_i-1}$ where we have used $f(p_i)={p_i}^{p_i-1}$ Considering this for all $i$ we get that $f({\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}})=\prod_{i=1}^{k}{{p_i}^{a_i}\prod_{j=1}^{s}{{c_j}^{d_j}}}}$ Here $\prod_{j=1}^{s}{{c_j}^{d_j}}$ divides $p_i-1$ for all $i$. Then by property (a) we have $\prod_{i=1}^{k}{(a_i+1)} \prod_{j=1}^{s}{(d_j+1)}={\prod_{i=1}^{k}{{p_i}^{a_i}}}$. So $\prod_{j=1}^{s}{(d_j+1)}$ divides ${\prod_{i=1}^{k}{{p_i}^{a_i}}}$ which means that there exists an $i$ such that $d_1 \equiv -1\pmod{p_i}$ so $d_1 \ge p_i-1$.This means that ${c_1}^{d_1}\ge {c_i}^{p_i-1}>p_i-1$. But note that $\prod_{j=1}^{s}{{c_i}^{d_i}}|(p_i-1)$ so ${c_1}^{d_1} \le \prod_{j=1}^{s}{{c_i}^{d_i}} \le p_i-1$.This contradicts our previous result. Thus $f({\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}})=\prod_{i=1}^{k}{{p_i}^{a_i}}}$. Now take $x={p_i}^{\alpha_i}$ and $y=\prod_{j \neq i}{p_j^{\alpha_j}}$.We will get $f({\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}})|({p_i}^{\alpha_i}-1)(\prod_{j \neq i}{{p_j}^{\alpha_j}})^{\prod_{i=1}^{k}{{p_i}^{\alpha_i}}-1}{p_i}^{{p_i}^{\alpha_i}-1}}$ So the $a_i$ never exceeds ${p_i}^{{\alpha}_i}-1$ for all $i$ so ${\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}}=\prod_{i=1}^{k}{(a_i+1)} \le {\prod_{i=1}^{k}{{p_i}^{{\alpha}_i}}}}$ and hence $a_i={p_i}^{{\alpha}_i}-1$.So multiplicativity is established. Finally the function is defined as $f(1)=1,f({p}^{{\alpha}})={p}^{{p}^{\alpha}-1}$ and $f$ is multiplicative.

This is a very standard problem. I will use repeatedly that $x^{y-1}$ can't divide $y-1$ (because it's bigger), and also that if $p|f(n)$ then the exponent of $p$ must be of the form $d-1$ where $d|n$. By condition 1. Note that, in particular, if $x$ is the smallest prime divisor of $n$, then $p^{x-1} | f(n)$. Firstly notice that for $r$ prime, $f(r)=s^{r-1}$ for some $s$ prime. Assume $s \neq r$. Now take $p>r,s$ a prime such that $p-1$ isn't divisible by $r$ nor $s$ (which can be done by CRT and Dirichlet). If $r$ or $s$=2, then make sure $p-1$ isn't divisible by $4$: Now, assume $f(p)=q^{p-1}$ for a prime $q$. Take any prime $a|f(pr)$. By first condition, $a^{r-1}|f(pr)$. If $a \neq q,s$ then $a^{r-1} | f(pr) | (r-1)s^{r-1}p^{big}$. But $a^{r-1}>r-1$, and therefore $a=p$. Then $a^{r-1}=p^{r-1} | (p-1)q^{p-1}r^{big}$, and since $a \neq q$, we get that $p=a=r$, contradiction to the definition of $p$. Therefore only $q,s$ divide $f(pr)$. Assume $s=q$, then $s^{pr-1}=f(pr) | s^{r-1}(r-1)p^{big}$ and so $s^{pr-r} | (r-1)p^{big}$ and since $s^{pr-r}>r-1$, we get $s=p$. Therefore, $p^{pr-1} = f(pr) | q^{p-1}(p-1)r^{big}$, so $p^{pr-1} | q^{p-1}$, contradiction. Therefore $s \neq q$. Now, if $s | f(pr)$ then $s^{r-1} | f(pr) | q^{p-1}(p-1)r^{big}$ and so $s^{r-1} | p-1$ and so, since we had said that $s$ didn't divide $p-1$ if $s$ was odd and $4$ didn't divide $p-1$, we get that $s=r=2$, contradiction since $s \neq r$. Therefore $s$ doesn't divide $f(pr)$ and so $f(pr)=q^{pr-1} | s^{r-1}(r-1)p^{big}$ and so $q=p$ and so $p^{pr-1} | q^{p-1}(p-1)r^{big}$, impossible. Finally we have a contradiction! So $\boxed{f(r)=r^{r-1}}$ for all $r$ prime. Now let $r | f(p^k)$ for $r,p$ primes. Then $r^{p-1} | (p-1)p^{p-1}(p^{k-1})^{p^k-1}$ and since $r^{p-1}>p-1$, we get $r=p$. Therefore $f(p^k)=p^{p^k-1}$ for all $p$ prime. Now let $p | f(m)$ be a prime that divides some $f(m)$. Let $x$ be the smallest prime divisor of $m$. If $p$ doesn't divide $m$, then $p^{x-1} | f(m) | (m/x)^{big}x^{x-1}(x-1)$ and so $p^{x-1} | (x-1)$, contradiction. So $p|m$, and let $x=p^a||m,y=m/x$. Then if $p^b || f(m)$, we get $p^b | (p^a-1)(f(p^a))$ and so $p^b | p^{p^a-1}$ and so $b \le p^a-1$. However, since this happens for all $p|f(m)$, and by condition 1 we get that $b=p^a-1$ for all $p|f(m)$. Therefore $f(m) = \prod_{p^a||m} f(p^a)$. So we are done and the answer is $\boxed{f(\prod p_i^{a_i}) = \prod p_i^{p_i^{a_i}-1}}$. Oh, and $f(1)=1$ clearly.

The important step in this problem is showing that $f(p^k) = p^{p^k-1}$, for the problem is not so hard after that. Here's a very straightforward, "just do it" style solution. There is only one clever step in here, and it is not too hard to notice once you see the condition. It should remind you of how we count the number of divisors of a number. Observe that the condition rearranges to \[ v_p(f(xy)) \le v_p(x-1) + (xy-1)v_p(y) + v_p(f(x)) \]This condition is trivial for all primes dividing $y$, so we will consider $v_p(f(xy)) \le v_p(x-1) + v_p(f(x))$ for all primes not dividing $y$.Observe that, for any prime $q$, \[ (q^n + 1)(q^n) = d(f((q^n+1)(q^n))) \] Taking $p = q$, $y = q^n + 1$, and $x = q^n$ gives that the latter is \[ \prod_{p}(1+v_p(f(q^n(q^n+1)))) \] \[ =(1+v_q(f(q^n)(q^n+1))) \times \prod_{p \neq q} (1+v_p(f(q^n)(q^n+1))) \] Since $v_p(x-1) = 0$, Now, observe that $p \nmid q^n$, so \[ (1+v_p(f((q^n)(q^n+1))) \le (1 + v_p(q^n) + v_p(f(q^n+1)) = 1 + v_p(f(q^n+1)) \]. Hence, the previous product is \[\le (1 + v_q(f(q^n)(q^n+1))) \times \prod_{p \neq q} (1 + v_p(f(q^n+1))) \]\[ \le (1 + v_q(f(q^n)(q^n+1))) \times d(f(q^n+1)) \] \[ = (q^n+1)(1 + v_q(f(q^n)(q^n+1)) \] Hence, we obtain the result \[ v_q(f((q^n)(q^n+1)) \ge q^n-1 \]Now, observe that \[ q^n - 1 \le v_q(f((q^n)(q^n+1)) \le v_q(q^n-1) + v_q(f(q^n)) = v_q(f(q^n))\] , but in fact equality must hold, since $d(f(q^n)) = q^n$! Hence, we obtain $f(q^n) = q^{q^n-1}$.

my solution: f(1)=1,f(2)=p $ f(2p)|p^{2p} $ d(f(2p))=2p => $ f(2p)=p^{2p-1} $ $ f(2q)|pq^{2q-1} $ =>$ f(2q)=q^{2q-1} , pq^{q-1} $ (p,2) : $ p^{2p-1}|(p-1)2^{2p-1}f(p) $ if $ p \neq 2 $ => p is no solution => p=2 in the same way,we can know that $ f(2q)=2q^{q-1} $ (q,2) : $ 2q^{q-1}|(q-1)2^{2q-1}f(q) $ =>$ f(q)=q^{q-1} $ (q,q) : $ f(q^2)=q^{q^2-1} $ simily we have $ f(q^{k})=q^{q^{k}-1} $ replace (x,y) to $ (p_{0}^{k_{0}} , p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}) $ and its cycle we can have: $ f(p_{0}^{k_{0}}p_{1}^{k_{1}}...p_{n}^{k_{n}})=p_{0}^{p_{0}^{k_{0}-1}}p_{1}^{p_{1}^{k_{1}-1}}...p_{n}^{p_{n}^{k_{n}-1}} $

As $d(f(1))=1$, we have $f(1)=1$. As $d(f(2))=2$, we get that $f(2)$ is a prime. Let $p\ge 3$ be a prime. As $f(2p)|p^{2p-1}f(2)$, from $d(f(2p))=2p$ we get that either $f(2p)=p^{2p-1}$ or $f(2p)=p^{p-1}f(2)$, so $p^{p-1}|f(2p)$. So $p^{p-1}|f(2p)|(p-1)2^{2p-1}f(p)$ which, combined with $d(f(p))=p$, yields $f(p)=p^{p-1}$. This forces $f(2p)=p^{p-1}f(2)$; we have that $f(2)|(p-1)2^{2p-1}$. If $f(2)\ne 2$, as $f(2)$ is a prime, we get that $f(2)|p-1$ for any prime $p\ge 3$. It is enough to choose $p\equiv 2(\mathrm{mod}\ f(2))$ to obtain a contradiction, so $f(2)=2$. We have that $f(p^k)|(p-1)p^{p-1}\left (p^{k-1} \right )^{p^k-1}$. Let $q$ be a prime divisor of $f(p^k)$. As $d(f(p^k))=p^k$, we get that $v_q(f(p^k))=p^\alpha-1\ge p-1$. If $q|p-1$, then $q\ne p$, so $q^{v_q(f(p^k))}|p-1$. But $q^{v_q(f(p^k))}\ge q^{p-1}\ge 2^{p-1}>p-1$, a contradiction, so $q=p$. We thus get that $f(p^k)$ is a power of $p$; from $d(f(p^k))=p^k$ we get that $f(p^k)=p^{p^k-1}$. Let $n\in \mathbb{N}$ be a number with at least two prime divisors, $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k}$ with $p_1<p_2<...<p_k$. We have that $f(n)|(p_1-1)p_1^{p_1-1}\left ( p_1^{\alpha-1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k} \right )^{n-1}$. Let $q$ be a prime dividing $f(n)$. As $d(f(n))=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k}$ we have that $v_q(f(n))=p_{i_1}^{\beta_1}\cdot p_{i_2}^{\beta_2}\cdot... \cdot p_{i_t}^{\beta_t}-1\ge p_1-1$. If $q|p_1-1$, then $q<p_1<p_2<...<p_k$, so $q^{v_q(f(n))}|p_1-1$, which is a contradiction because $q^{v_q(f(n))}\ge q^{p_1-1}\ge 2^{p_1-1}>p_1-1$. Therefore $(q,p_1-1)=1$, hence $q\in \{ p_1,..,p_k\}$. Thereby, any prime divisor of $f(p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k})$ can be found in the set $\{p_1,p_2,..., p_k\}$.

We claim that $f(n)$ is a multiplicative function with $f(p^k)=p^{p^k -1 }$. Clearly $f(1)=1$. Lemma 1: For primes $p$, $f(p)=p^{p-1}$. Proof: Note that $f(p)$ is the $p-1$th power of some prime. WLOG $p> q$. Now, note that $f(pq)\mid (p-1)\cdot q^{pq-1}\cdot f(p)$ and $f(pq)\mid (q-1)\cdot p^{pq-1}\cdot f(q)$. Note that $f(pq)$ is either of form $a^{pq-1}$ or $b^{p-1}\cdot c^{p-1}$; i.e., $f(pq)$ has at most two prime divisors. Suppose $f(pq)$ had only one prime divisor; i.e. it was the $pq-1$th power of a prime. Then that $pq-1$th power must divide both $(p-1)\cdot q^{pq-1}\cdot f(p)$ and $(q-1)\cdot p^{pq-1}\cdot f(q)$. Note that $p-1$ and $q-1$ are both too small to have their own $pq-1$th power, and similarly with $f(p)$ and $f(q)$ (because they are $p-1$ and $q-1$th powers, respectively). But this means that $f(pq)\mid q^{pq-1}$ and $f(pq)\mid p^{pq-1}$, which is a contradiction! Thus $f(pq)$ has two prime divisors. By the second divisibility relation, these primes must be $p$ and the prime dividing $f(q)$. Indeed, $q-1$ is not large enough to have a prime factor, distinct from that dividing $p$ or $f(q)$, for it to have a prime-adic valuation of $q-1$. But then this means $p\mid f(pq)$, so $p\mid (p-1)\cdot q^{pq-1}\cdot f(p)$. Thus $p\mid f(p)$. Since $f(p)$ is the $p-1$th power of a prime, $f(p)=p^{p-1}$. Note that if $p$ is an odd prime, then there is always a prime smaller than $p$, so we can repeat this process for all odd primes $p$. Next we show $f(2)=2$. Suppose $f(2)=P$ for some odd prime $P$. Then take $p$ with $P\nmid p-1$. Note that $f(2p)\mid p^{2p-1}\cdot P$, and $f(2p)\mid (p-1)\cdot 2^{2p-1}\cdot f(p)$. Note that $P\nmid f(2p)$, from the last relation, as $P\nmid f(p), p-1, 2$. Thus $f(2p)\mid p^{2p-1}$ from the first relation. It follows $f(2p)=p^{2p-1}$. But then $p^{2p-1}\mid (p-1)\cdot 2^{2p-1}\cdot f(p)$, a contradiction as $v_p(f(p))=p-1 < 2p-1$. Thus $f(2)=2$. $\blacksquare$ Lemma 2: $f(p^k) = p^{p^k-1}$. Proof: Note that $f(p^k)=f(p\cdot p^{k-1})\mid (p-1)\cdot \left(p^{k-1}\right)^{p^k-1} \cdot f(p)$. In other words, $f(p^k)$ divides $(p-1)\cdot p^r$ for some large $r$, by Lemma 1. Suppose $f(p^k)=(p-1)\cdot p^s$ for $s\le r$. But then $d(f(p^k)) = d(p-1)\cdot d(p^s)$. Note that $p\nmid d(p-1)$, as the p-adic valuation of any prime dividing $p-1$ must be less than $p-1$. Thus $f(p^k)$ is a power of $p$. It is easy to see, therefore, that $f(p^k) = p^{p^k-1}$, as desired. $\blacksquare$ Now we establish the multiplicativity. Suppose $n=\prod p_i^{e_i}$. We show that $f(n)=\prod f(p_i^{e_i})$. First, we establish that the set of primes dividing $f(n)$ is a subset of the set of primes dividing $n$. Let $p_1$ be the smallest prime dividing $n$. Then $f(n)=f\left(p_1\cdot n/p_1\right) \mid (p_1-1)\cdot (n/p_1)^{n-1}\cdot f(p_1)=(p_1-1)\cdot (n/p_1)^{n-1}\cdot p_1^{p_1-1}$. Now, if some integer $m\mid f(n)$ and $m$ does not divide $n$, then $m\mid p_1-1$. But then the $p$-adic valuation of $m$ is strictly less than $p_1-1$ for any prime $p$, and thus $d(m)$ is relatively prime to $p_1,..., p_k\mid n$. In particular, $d(m)\mid d(f(n))=n$, a contradiction unless $d(m)=1$, or $m=1$. Thus the only integer $m$ such that $m\mid f(n)$ and $m$ doesn't divide $n$ is $m=1$. Now we show that $v_{p_i} (f(n))\le p_i^{e_i} - 1$. Indeed, take $p=p_j$ and $e=e_j$ for some $j$ and $p_j\mid n$. Then $f(n)=f(p^e\cdot n/p^e)\mid \left(p^e-1\right)\cdot (n/p^e)^{n-1}\cdot f(p^e)$. Note that the $p$-adic valuation of the right side is $p^e-1$. Thus $v_{p_j} (f(n))\le p_j^{e_j} - 1$. But this implies that $d(f(n))\le \prod \left(p_i^{e_i} - 1 + 1\right) = n$. Thus each inequality must be an equality, so $v_{p_i}(f(n))=p_i^{e_i} - 1$. Moreover, since the set of primes dividing $f(n)$ is a subset of the primes dividing $n$, we have established that $f(n)=\prod p_i^{p_i^{e_i} - 1}$, as desired. It is easy to check that this $f$ works. $\square$

IMO ShortList 2008 N5 wrote: For every $ n\in\mathbb{N}$ let $ d(n)$ denote the number of (positive) divisors of $ n$. Find all functions $ f: \mathbb{N}\to\mathbb{N}$ with the following properties: $ d\left(f(x)\right) = x$ for all $ x\in\mathbb{N}$. $ f(xy)$ divides $ (x - 1)y^{xy - 1}f(x)$ for all $ x$, $ y\in\mathbb{N}$. Proposed by Bruno Le Floch, France

Nice illustration of my firm belief, "All (good) FEs are motivated!"

Please check my solution

Beautiful problem. Here's my solution: Let $P(x,y)$ denote the second condition given to us. We make a series of claims, which will help us in discovering $f(x)$. CLAIM-1| $f(1)=1$ and $f(2)=2$. Proof of Claim As $d(f(1))=1$, so we directly get that $f(1)=1$. Let $f(p)=p_1^{e_1}p_2^{e_2} \dots p_n^{e_n}$, for some primes $p,p_1,p_2, \dots ,p_n$. Then $$d(f(p))=p \Rightarrow (e_1+1)(e_2+1) \dots (e_n+1)=p \Rightarrow e_1=p-1,e_2=0,e_3=0, \dots ,e_n=0$$Thus, we get that, for all primes $p$, $f(p)=q^{p-1}$, for some prime $q$. Taking $p=2$, we have $f(2)=q$. Now, We have that $$P(2,q) \Rightarrow f(2q) \mid q^{2q-1} \cdot f(2) \Rightarrow f(2q) \mid q^{2q} \Rightarrow f(2q)=q^a \text{ for some } 0 \leq a \leq 2q$$But, as $d(f(2q))=2q$, so $a+1=2q \Rightarrow a=2q-1$. However, taking $f(q)=q_1^{q-1}$ for some prime $q_1$, we get that $$P(q,2) \Rightarrow f(2q) \mid (q-1) \cdot 2^{2q-1} \cdot f(q) \Rightarrow q^{2q-1} \mid (q-1) \cdot 2^{2q-1} \cdot q_1^{q-1} \Rightarrow q=2$$where the last statement follows using the fact that $\gcd(q^{2q-1},q-1)=1$. Thus, our claim is true. $\Box$ CLAIM-2| For all primes $p$, we have $f(p)=p^{p-1}$. Proof of Claim We already showed (while proving Claim-1), that for all primes $p$, $f(p)=q^{p-1}$, for some prime $q$. We have already showed that this claim is true for $p=2$. So from now on assume that $p$ is an odd prime. Then, using Claim-1, we get that $$P(2,p) \Rightarrow f(2p) \mid 2p^{2p-1} \Rightarrow f(2p)=2^ap^b \text{ for some } o \leq a \leq 1 \text{ and } 0 \leq b \leq 2p-1$$But, as $d(f(2p))=2p$, so we have $(a+1)(b+1)=2p$. When $a=0$, we have $b=2p-1$, and when $a=1$, we have $b=p-1$. Thus, we get that $p^{p-1} \mid f(2p)$ in both the cases. This gives $$P(p,2) \Rightarrow f(2p) \mid (p-1) \cdot 2^{2p-1} \cdot f(p) \Rightarrow p^{p-1} \mid (p-1) \cdot 2^{2p-1} \cdot q^{p-1} \Rightarrow q=p$$where the last statement follows from our assumption that $p$ is odd, and the fact that $\gcd(p^{p-1},p-1)=1$. Thus, our claim is true. $\Box$ CLAIM-3| For all primes $p$ and positive integers $m$, we have $f(p^m)=p^{p^m-1}$. Proof of Claim Using Claim-2, we can see that $$P(p,p^{m-1}) \Rightarrow f(p^m) \mid (p-1) \cdot p^{(m-1)(p^m-1)} \cdot p^{p-1}$$Suppose, to the contrary, there exists a prime $p_0 \neq p$ such that $p_0^{e_0} \mid f(p^m)$ for some $e_0 \in \mathbb{N}$. Then, $e_0+1 \mid d(f(p^m))=p^m$, which gives that $e_0=p^k-1$ for some $1 \leq k \leq m$. Then, by the above condition, we have that $$p_0^{e_0} \mid f(p^m) \mid (p-1)p^{(m-1)(p^m-1)+p-1} \Rightarrow p_0^{p^k-1} \mid p-1 \Rightarrow p-1 \geq p_0^{p^k-1} \geq p_0^{p-1}$$But, by FLT, we get that $$p \mid p_0^{p-1}-1 \Rightarrow p_0^{p-1} \geq p+1>p-1 \rightarrow \text{CONTRADICTION}$$Thus, we must have $f(p^m)=p^s$ for some positive integer $s$. Then, as $d(f(p^m))=p^m$, so we have $s+1=p^m$, thus proving our claim. $\Box$ CLAIM-4| Let $p$ be a prime divisor of $f(n)$ for some positive integer $n$. Then $p \mid n$. Proof of Claim Suppose, to the contrary, $p \nmid n$. Let $\nu_p(f(n))=k$. Then $k+1 \mid d(f(n))=n,$ which means that some prime divisor of $n$ (say $q$) divides $k+1$ also. Then we have $$q \mid k+1 \Rightarrow q \leq k-1 \Rightarrow p^{q-1} \mid p^k \mid f(n) \Rightarrow \text{By } P \left(q, \frac{n}{q} \right) \text{, we get that } p^{q-1} \mid f(n) \mid (q-1) \cdot n^{qn-1} \cdot q^{q-1}$$As $\gcd(p,n)=\gcd(p,q)=1$, we get that $p^{q-1} \mid q-1$. However, by FLT, we have that $$q \mid p^{q-1}-1 \Rightarrow p^{q-1} \geq q+1>q-1 \Rightarrow p^{q-1} \nmid q-1 \rightarrow \text{CONTRADICTION}$$Thus, our assumption must be wrong, which gives that $p \mid n$, hence proving our claim. $\Box$ CLAIM-5| $f$ is multiplicative on coprime integers, or equivalently, we have $f(p_1^{m_1}p_2^{m_2}...p_r^{m_r})=f(p_1^{m_1})f(p_2^{m_2}) \dots f(p_r^{m_r})$ for primes $p_1,p_2, \dots p_r.$ Proof of Claim Let $p_1^{m_1}p_2^{m_2} \dots p_r^{m_r}=n$. By Claim-4, we have that $f(n)=p_1^{k_1}p_2^{k_2} \dots p_r^{k_r}$ for non-negative integers $k_1,k_2, \dots ,k_r$. Note that, using Claim-3, we have that $$P(p_r^{m_r},p_1^{m_1}p_2^{m_2} \dots p_{r-1}^{m_{r-1}}) \Rightarrow p_1^{k_1}p_2^{k_2} \dots p_r^{k_r}=f(n) \mid (p_r^{m-r}-1)(p_1^{m_1}p_2^{m_2} \dots p_{r-1}^{m_{r-1}})^{n-1} \cdot f(p_r^{m_r}) \Rightarrow p_r^{k_r} \mid p_r^{p_r^{m_r}-1} \Rightarrow k_r \leq p_r^{m_r}-1$$Repeating this same argument, one easily gets that $k_i+1 \leq p_i^{m_i}$ for all $i \in \{1,2, \dots ,r\}$. Then we have $$\prod_{i=1}^r (k_i+1)=d(f(n))=n \Rightarrow n \leq \prod_{i=1}^r p_i^{m_i}=n \text{, which means that equality must hold in all cases.}$$Thus, we get that $k_i=p_i^{m_i}-1$, hence proving our claim (using Claim-3). $\Box$ So finally we can determine all such functions $f$ by $$\boxed{f(1)=1,f(p^m)=p^{p^m-1} \text{ and } f \text{ is multiplicative.}}$$

Wow, what a problem... nothing non-elementary, yet... anyhow here's my solution, which I've tried to make as "motivated" as possible... First, let $P(x,y)$ denote $f(xy) \mid (x-1)y^{xy-1}f(x)$, and there's no real point keeping $Q(x)$ as $d(f(x))=x$, so we won't. Before we try to really attack the problem, let's try and get the obvious down- $f(1)=1$, by $Q(1)$, $f(2)$ must be prime, $f(p)$ must be $q^{p-1}$ for some primes $p$ and $q$... Hmm, we can already get a feel that the problem must heavily rest on primes, as such questions usually tend to. So, considering there really isn't too much information to go by, perhaps let's begin with the only concrete information we have about a particular number- in other words, let's try to figure out what we could do with $f(2)=r$ ($r$ prime). $$P(2,r): f(2r) \mid r^{2r}$$As $d(f(2r))=2r$, and the only prime factor of $f(2r)$ is $r$, thus $f(2r)=r^{2r-1}$ Now, naturally the next substitution would be $(r,2)$, so: $$P(r,2): f(2r)=r^{2r-1} \mid (r-1)2^{2r-1}f(r)=>r^{2r-1} \mid 2^{2r-1}f(r)$$Say $r \neq 2$- Thus $r^{2r-1} \mid f(r)$, and as $f(r)=q^{r-1}$ for prime $q =>$ Contradiction, as $r$ is prime. Hence $f(2)=2$. Now comes the time for the key substitutions that we will spam throughout the rest of the solution- $P(2,y)$ and $P(x,2)$. First let's take some $x=p^n$, for prime $p$ and integer $n$- $$P(2,p^n): f(2p^n) \mid 2(p^n)^{2p^n-1}$$As only possible prime factors of $f(2p^n)$ are $2$ and $p$, and $d(f(2p^n))=2p^n$, thus $f(2p^n)=p^{2p^n-1}$ or $2p^{p_n-1}$. But, as $$P(p^n,2): f(2p^n) \mid 2^{2p^n-1}(p^n-1)f(p^n)$$Hence, if $f(2p^n)=p^{2p^n-1} =>p^{2p^n-1} \mid f(p^n)$- but as $d(f(p^n))=p^n=>$ Contradiction. Thus $\boxed{f(2p^n)=2p^{p^n-1}}$. Again, as $f(2p^n)=2p^{p^n-1} \mid 2^{2p^n-1}(p^n-1)f(p^n) =>p^{p^n-1} \mid f(p^n)$. As $d(f(p^n))=p^n=>\boxed{f(p^n)=p^{p^n-1}}$. Till here we had a relatively smooth sail, at least after we got hold of the key idea- now we must be really careful, as going down the wrong path could really lead to some un-understandable mess, especially since we're dealing with towers of powers here... Anyway, the key observation here comes with playing with $P(p^ny,2)$ and $P(2p^n,y)$ and its variants and building an inductive argument from this- first let's just write down all these aforementioned variants and see if we get something- $$P(2p^n,y): f(2p^ny) \mid (2p^n-1)y^{2p^ny-1} \cdot 2p^{p^n-1}$$$$P(y,2p^n): f(2p^ny) \mid (y-1)f(y)2^{2p^ny-1}p^{n(2p^ny-1)}$$$$P(2,p^ny): f(2p^ny) \mid 2p^{n(2yp^n-1)} y^{2yp^n-1}$$$$P(p^ny,2): f(2p^ny) \mid (p^ny-1) 2^{2p^ny-1}f(p^ny)$$Hmm... so the idea here is to build a sort-of inductive argument using $gcd(p,y)=1$, building $x$ out of prime powers (this is also why we proved $f(p^n)=p^{p^n-1}$ for a prime power, not simply for a prime $p$)- thus we can let $y=q_1^{\alpha_1}q_2^{\alpha_2}...q_k^{\alpha_k}$, assuming $f(y)=q_1^{q_1^{\alpha_1}-1}...q_k^{q_k^{\alpha_k}-1}$. Let's now try to set restrictions on the powers of primes dividing $f(p^ny)$, and then try to sneak in $d(f(x))$ somewhere. First, notice by equation $3$, the only prime divisors of $f(2p^ny)$ are $2,p,q_1,q_2,...,q_k$ and $v_2(f(2p^ny) \leq 1$. Moreover, by equation $1$, $v_p(f(2p^ny)) \leq p^n-1$ and by equation $2$, $v_{q_i}(f(2p^ny) \leq q_i^{\alpha_i}-1$. Now, perhaps, we have enough to finish this off- observe $f(2p^ny)=2p^{p^n-1}q_1^{q_1^{\alpha_1}-1}...q_k^{q_k^{\alpha_k}-1}$ satisfies $d(f(2p^ny)) =2p^ny$, and it's easy to see that it's the only value of $f(2p^ny)$ that satisfies $d(f(2p^ny))=2p^ny$ (if there was some other value, then this must mean that one of the powers of primes of this other $f(2p^ny)$ must be larger than the power on the prime of our old $f(2p^ny)$, which is of course impossible by our bounds.

- in other words, we've only found $f(x)$ for odd $x$. Luckily for us, the even part becomes relatively simple once the odd part's done, and this is what we'll attempt to prove here. First, following the $P(2,2^n)$ tradition, we get $f(2^{n+1}) \mid 2 \cdot 2^{n(2^{n+1}-1)} =>2$ is the only prime divisor of $f(2^{n+1}$. As $d(f(2^n))=2^n$, we get $f(2^n)=2^{2^n-1}$. Now the rest of the argument remains the same, but instead of having to multiply by an arbitrary $p^n$, we do it with a more concrete $2^n$. And now, finally, we're truly done, and hence our solution holds as: $f(n)$, for $n=p_1^{\alpha_1}...p_k^{\alpha_k}$, equals $p_1^{p_1^{\alpha_1}-1}p_k^{p_2^{\alpha_2}-1}...p_1^{p_k^{\alpha_k}-1}$, and this indeed works.

harazi wrote: Indeed, a terrible problem! Solved with william122. The unique function $f$ is constructed as follows: $f(p^e) = p^{p^e - 1}$, and $f$ is multiplicative. (So for instance, $f(6) = f(2)f(3) = 2 \cdot 3^2$.) This evidently satisfies the first condition, and for any prime that divides $xy$ $$\nu_p(xy) = p^{\nu_p(xy)} - 1 < xy-1 \leq \nu_p(y^{xy-1})$$if $p \mid y$. If not, then $p^{\nu_p(xy)} - 1 = p^{\nu_{p}(x)} - 1 = \nu_p(f(x))$, so $f$ works. We now show that it is unique. Evidently $f(1) = 1$. The primary claim is the following. Claim 1. For all primes $p$, $f(p) = p^{p-1}$. Proof. Pick a prime $q$ for which $p-1 < 2^{q-p}$. Then the second condition gives us $f(p \cdot q)$ divides $(p-1) q^{pq - 1} f(p)$, and $f(q \cdot p)$ divides $(q-1) p^{pq - 1} f(q)$. Because $d(f(pq)) = pq$, we have $f(pq) \in \{a^{pq - 1}, a^{q-1}b^{p-1}\}$ for primes $a$ and $b$; either way, there must exist a prime $a$ such that $\nu_a(f(pq)) \geq q-1$. So $a^{q-1} \mid (p-1) q^{pq-1} f(p)$, id est $a = q$ or $a^{q-1} \mid (p-1)f(p)$. But $(p-1)f(p) < 2^{q-p}f(p)$, so the latter case is impossible. Thus, $$q^{a-1} \mid f(q \cdot p) \mid (q-1) p^{pq - 1} f(q),$$which yields $f(q) = q^{q-1}$ and $\nu_q(f(pq)) = q^{q-1}$. Then plugging back into the first equation gives $f(pq) = p^{p-1}q^{q-1}$, and thus $f(p) = p^{p-1}$. Claim 2. For all primes $p$, $f(p^e) = p^{p^e - 1}$. Proof. Note that $$f(p \cdot p^{e-1}) = (p-1)p^{(e-1)(p^e - 1)} p^{p-1}.$$Moreover, all primes $a \mid f(p^e)$ must satisfy $\nu_a(f(p^e)) \geq p-1$ by Condition 1. Evidently $2^{p-1} > p-1$, so $f(p^{e})$ is a power of $p$, which quickly yields the desired. Claim 3. $f$ must take on the aforementioned form. Proof. We use induction on the number of prime factors (with multiplicity); $f(1) = 1$ is vacuous, and $f(p) = p^{p-1}$ by our first claim. As for the inductive step, if $p$ is the least prime factor of $n$ and $\nu_p(n) = e$, then $f(p^e \cdot n/p^e) \mid (p^e-1)(n/p^e)^{n-1} p^{p^e-1}$, and $f(n/p^e \cdot p^e) \mid (n/p^e - 1)p^{e(n-1)} f(n/p^e)$. Then by the hypothesis, $f(n) \mid p^{p^{e} -1} f(n/p^e)$, yielding $f(n) = p^{p^{e} - 1} f(n/p^e)$ by the first condition. The end. $\square$ Remark. The presence of the $(x-1)$ factor in Condition 2 is only there so substituting $x = 1$ doesn't kill the problem.

Let $x=p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n}$ be the prime factorization of $x$. Then we claim that $$f(x)=\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$Obviously $d(f(x))=x$, now let $p_1,...,p_n$ be the prime factors of $xy$. WLOG assume $p_1,...,p_m$ are also prime factors of $y$, then we have $$v_{p_i}(f(xy))=p_i^{\alpha_i-1}\leq xy-1=v_{p_i}(y^{xy-1})\leq v_{p_i}((x-1)y^{xy-1}f(x))$$for eachi $1\leq i\leq m$. If $m+1\leq i\leq n$, then we have $$v_{p_i}(f(xy))=p_i{\alpha_i-1}=v_{p_i}(f(x))\leq v_{p_i}((x-1)y^{xy-1}f(x))$$this shows that $f$ also satisfies condition (ii). Lable the equation \begin{align} f(xy)|(x-1)y^{xy-1}f(x) \end{align} Firstly since $d(f(p))=p$ we must have $f(p)=q^{p-1}$ for some prime $p$. CLAIM 1. $f(p)=p^{p-1}$ for all prime $p$. Proof. It suffices to show that $(f(p),p)\neq 1$. Suppose on the contrary that $(f(p),p)=1$. Pick a number $r$ such that $(r,p)=1$. Therefore, sub. $x=p$ and $y=r$ in $(1)$ we have $$f(pr)|(p-1)r^{pr-1}f(p)$$Notice that the the g.c.d. of the right hand side and $p$ is 1. Hence $(f(pr),p)=1$. Now swapping $p$ and $r$ we have $$f(pr)|(r-1)p^{pr-1}f(r)$$hence $$f(pr)|(r-1)f(r) $$If $p\geq 3$, then by Dirichlet's theorem there exists a prime $s$ with $s\equiv 1\pmod p$. Let $r=s+1$, then $(r,p)=1$. Hence $$f(pr)|sf(r)$$But then $$pr=d(f(pr))\leq d(sf(r))\leq d(s)d(f(r))=2r$$which is a contradiction since $p\geq 3$. In particular, $f(3)=9$. Therefore, suppose $(f(2),2)=1$, we have $$f(2\cdot 3)|(3-1)f(3)=18$$Since $d(f(6))=6=d(18)$ we must have $f(6)=18$. Now sub $x=2$, $y=3$ in $(1)$ we have $$18=f(6)|3^5f(2)$$Hence $(f(2),2)\neq 1$, contradiction. $\blacksquare$ CLAIM 2. $f(p^n)=p^{p^n-1}$ for all positive integer $n$ and prime $p$. Proof. The case $n=1$ is exactly CLAIM 1. Now assume $n\geq 2$. Sub. $x=p$ and $y=p^{n-1}$ in $(1)$ We have $$f(p^n)|(p-1)(p^{n-1})^{p^n-1}p^{p-1}$$Let $q=(p-1,f(p^n))$, $r=\frac{f(p^n)}{q}$, then we have $(d,r)=1$. It suffices to show $q=1$. Otherwise we have $2\leq d(q)\leq p-1$. Moreover $$p^n=d(f(p^n))=d(q)d(r)$$Hence $p^n$ has a factor smaller than $p-1$ and larger than $d(q)$, contradiction. Now we put together CLAIM 1 and CLAIM 2 to prove the case $n=1$. Now let $k=p_1^{\alpha_1}p_2^{\alpha_2}...p_n^{\alpha_n}$. WLOG assume $p_1<p_2<...<p_n$ CLAIM 3. $v_{p_i}f(k)\leq p_i^{\alpha_i}-1$ Proof. sub. $x=p_i^{\alpha_i}$ and $y=\frac{k}{x}$ into $(1)$. Then $$f(k)|(x-1)y^{k-1}p_i^{p_i^{\alpha_i}-1}$$Notice that $((x-1)y^{k-1}, p_i)=1$, this completes the proof of the claim. $\blacksquare$ Therefore, using CLAIM 3 and letting $x=p_1$ and $y=\frac{k}{p_1}$ we have $$f(k)|(p_1-1)\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$We use the same trick as in CLAIM 2, let $q=(f(k),p_1-1)$ and $r=\frac{f(k)}{q}$. Suppose on the contrary that $q\neq 1$, then $$k=d(f(k))=d(q)d(r)$$Since $d(q)\leq q\leq p_1-1$. This implies that $k$ has a prime factor less than $p_1$ which is a contradiction. Hence $q=1$. This implies $$f(k)|\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$Since $d(\prod_{i=1}^np_i^{p_i^{\alpha_i-1}})=k$, we must have $$f(k)=\prod_{i=1}^np_i^{p_i^{\alpha_i-1}}$$as desired.

Let $P(x,y)$ denote the second assertion.At first few observations about $f$: $d(f(1))=1\implies f(1)=1$ For all odd prime $p$ $d(f(p))=p\implies f(p)=\text{(prime)}^{p-1}$ and $d(f(2))=2\implies f(2)=\text{prime}$ For any odd prime $p$,$P(2,p)$ gives $f(p)|p^{2p-1}f(2)$ and as $f(2)$ is only a prime hence $f(p)=p^{p-1}$ If $f(2)=q$,a odd prime then,$$P(2,q):f(2q)|q^{2q}$$and $d(f(2q))=2q$ gives $f(2q)=q^{2q-1}$.But$$P(q,2):f(2q)=2^{2q-1}|(q-1)2^{2q-1}q^{q-1}\implies q^{q}|(q-1)2^{2q-1}$$It is a contradiction,Hence,$f(2)=2$ Claim:For prime $q\nmid n\implies q\nmid f(n)$ Proof.FTSOC,assume $q\nmid n$ but $q^r||f(n)$.$p$ is the least prime divisior of $n$.Then $P(p,\frac{n}{p})$ gives:$$q^r||f(p. \frac{n}{p})|(p-1)(\frac{n}{p})^{n-1}p^{p-1}\qquad {(*)}$$Also,as $d(f(n))=n,$ hence $r+1|n\implies r\ge p-1$.But then,$q^{r}\ge q^{p-1}>p-1$.Contradicting $(*)$,since $gcd(q,(\frac{n}{p})^{n-1}p^{p-1})=1$$\blacksquare$ So from the claim and from $d(f(p^m))=p^m$ we get $f(p^m)=p^{p^m-1}$ Finally,we will prove by induction on $n$ that if $n=p_1^{a_1}p_2^{a_2}\dots p_r^{a_r}$ then $f(n)=\prod_{i=1}^ r p_i^{p_i^{a_i}-1}$ For $p|n$ with $v_p(n)=r$ we have by $P(p^r,\frac{n}{p^r})$and $P(\frac{n}{p^r},p^r)$: $$f(n)|(p^r-1)(\frac{n}{p^r})^{n-1}p^{p^r-1}\qquad (1)$$$$f(n)|(\frac{n}{p^r}-1)p^{r(n-1)}.f(\frac{n}{p^r})\qquad (2)$$ So $f(n)$ devides the GCD of above 2.Also,by the claim we can simply discard any common divisor of $(p^r-1),(n/p^r-1)$ that does not devide $n$.Hence,$f(n)|p^{p^r-1}.f(\frac{n}{p^r})$.But then by size issue on $d(f(n))=n$[and induction hypothesis on $f(\frac{n}{p^r})$ and uniqueness of prime factorisation $f(n)=p^{p^r-1}.f(\frac{n}{p^r})$ $\blacksquare$.

Solved with gabrupro The answer is a multiplicative function $f$ defined on primes as $f(p^k) = p^{p^k - 1}$. This can be easily checked to work. Let $P(x,y)$ denote the second condition given. First, $f(1) = 1$ since $d(f(1)) = 1$ and say $f(2) = c$ for a prime $c$ since $d(f(2)) = 2$. Let $p$ be an odd prime. Claim 1: $f(p) = p^{p-1}$ and $c = 2$ Proof: $P(2, p)$ gives $f(2p) | cp^{2p-1}$ and $P(p,2)$ gives $f(2p) | (p-1)2^{2p-1}f(p)$. Since $d(f(2p)) = 2p$, we must have some prime $q$ dividing $f(2p)$ with $v_q$ at least $p-1$, so this can only be $p$. So we have either $f(2p) = cp^{p-1}$ or $f(2p) = p^{2p-1}$. But in the latter case, we have $p^{2p-1} = f(2p) | (p-1)2^{2p-1}f(p) \implies p^{2p-1} | f(p)$ meaning $p = d(f(p)) \ge 2p$, impossible. So we have $f(2p) = cp^{p-1}$ for all odd primes $p$. So we have $cp^{p-1} | (p-1)2^{2p-1}f(p)$ and so $p^{p-1} | f(p)$, which forces $f(p) = p^{p-1}$ for all primes $p$, picking $p = 3$, we have $9c | 64f(3) = 64(9) \implies c | 64 \implies c = 2$, so $f(2) = 2$ as well.$\square$ Claim 2: $f(p^k) = p^{p^k - 1}$ Proof: In duck. The base case is $k = 1$, suppose it is true until $k-1$, then we have, from $P(p,p^{k-1})$, that $f(p^k) | (p-1)p^{(k-1)(p^k - 1)}f(p) = (p-1)p^{(k-1)(p^k - 1) + p^{k-1} - 1} = (p-1)p^{kp^k - p^k - k}$. Suppose there existed a prime $q \neq p$ dividing $f(p^k)$, then we must have $q^{v_q(f(p^k))} | p-1$, but since the LHS is at least $2^{p-1}$, it is too big, so this is impossible. So $p$ is the only prime dividing $f(p^k)$ and so $f(p^k) = p^{p^k - 1}$, as claimed.$\square$ Claim 3: The set of primes dividing $f(n)$ is a subset of the primes dividing $n$ Proof: Let $n = pm$ such that $p$ is the smallest prime dividing $n$. Suppose there was a prime $q$ dividing $f(pm)$ but not $pm$. Then $P(p,m)$ gives $q^{v_q(f(pm))} | f(pm) | (p-1)m^{pm-1}p^{p-1} \implies q^{v_q(f(pm))} | p-1$ but LHS is again at least $2^{p-1} > p-1$, impossible. So indeed the claim follows.$\square$ Claim 4: $f$ is multiplicative Proof: Let $p$ be a prime dividing $n$ and suppose $n = p^km$ with $p \nmid m$. $P(p^k, m)$ gives $f(n) | (p^k - 1)m^{n-1}p^{p^k - 1}$, so we have $v_p(f(n)) \le p^k -1$, and so since $d(f(n)) = n$ and these are the only primes dividing $f(n)$ by claim 3, we have that $f$ is indeed of the claimed form and hence multiplicative. $\square$. So $f$ must be indeed of the said form, so we are done. $\blacksquare$

Writeup was pretty annoying ngl but a nice problem nevertheless.

This is a shortened version of the official solution that I found after reading the official solution. The main thing I will do here is directly reducing the problem to showing that $p \nmid n$ implies $p \nmid f(n)$. In this solution, the exact values $\nu_p(f(n))$ will not be that much important. The answer is \[ f\left(\prod_{i = 1}^k p_i^{a_i}\right) = \prod_{i = 1}^k p_i^{p_i^{a_i} - 1} \]for all distinct primes $p_1, \ldots, p_k$ and positive integers $a_1, \ldots, a_k$. One can directly check that this function works. The equality $d(f(x)) = x$ follows by the formula for number of divisors in terms of prime factorization. The second condition follows, for example, by checking $p$-adic valuations at each prime $p$. In fact, $f(xy)$ divides $y^{xy - 1} f(x)$ for any $x, y \in \mathbb{N}$. For the converse, it suffices to show that for any $p$ prime and $n \in \mathbb{N}$, \[ \nu_p(f(n)) \leq p^{\nu_p(n)} - 1. \]Then the condition $d(f(n)) = n$ will force equality at each prime since $\nu_p(k) + 1 \mid d(k)$ for any $k \in \mathbb{N}$ and $p$ prime. First, if $p$ divides $n$, take $x = p^{\nu_p(n)}$ and $y = n/x$. Then $p$ does not divide $x - 1$ and $y$, so the second condition implies \[ \nu_p(f(n)) \leq \nu_p(f(x)) = \nu_p(f(p^{\nu_p(n)})) \leq d(f(p^{\nu_p(n)})) - 1 = p^{\nu_p(n)} - 1. \]If $p$ divides $n$, the inequality is equivalent to saying that $p$ does not divide $f(n)$. Thus, it now remains to show that $p \nmid n$ implies $p \nmid f(n)$. We start by showing that $f(p) = p^{p - 1}$ for any $p$ prime. All we actually need is that the only prime divisor of $f(p)$ is $p$. Since $d(f(p)) = p$, $f(p) = q^{p - 1}$ for some $q$ prime. In particular, $f(2)$ is prime. We just need to show that $q = p$. If $p$ is odd, then the second condition implies that $f(2p)$ divides $p^{2p - 1} f(2)$ and $(p - 1) 2^{2p - 1} q^{p - 1}$. If $q \neq p$, then $p \nmid f(2p)$ and thus $f(2p) \mid f(2)$. But the first property implies $f(2p) > 1$. Since $f(2)$ is prime, we get $f(2p) = f(2)$; a contradiction since the first property implies that $f$ is injective. For $p = 2$, the second property implies that $f(6)$ divides $3^5 f(2)$ and $(3 - 1) 2^5 f(3) = 2^6 3^2$. If $f(2)$ is odd, then $f(6) \mid 9$. But then $6 = d(f(6)) \leq d(9) = 3$; a contradiction. Thus, $f(2) = 2$. Finally, we show that $p \nmid n$ implies $p \nmid f(n)$. Let $q$ be the smallest prime divisor of $n$. Clearly, $q \neq p$, so $\nu_p(f(q)) = 0$. Now plug $x = q$ and $y = n/q$ into the second property. Since clearly $p \nmid y$, we have \[ \nu_p(f(n)) \leq \nu_p(q - 1) + \nu_p(f(q)) = \nu_p(q - 1) < q - 1. \]On the other hand, $\nu_p(f(n)) + 1$ divides $d(f(n)) = n$. Since $\nu_p(f(n)) + 1 < q$, we necessarily have $\nu_p(f(n)) = 0$. Thus $p \nmid f(n)$, as desired.

let $P(x,y)$ denote the second condition we directly get that $f(1) = 1$ first we want to find $f(p)$, we know $f(p)$ has form $q^{p-1}$, additionally we know $f(2) = q$ from $P(2,p)$ and $ P(p,2)$ we get that $f(2p) \mid f(2)p^{2p-1}$ and $f(2p) \mid 2^{2p-1}(p-1)f(p)$, from the first one we get, noting that $d(f(2p)) = 2p$ that $f(2p)$ is either $p^{2p-1}$ or $f(2)p^{p-1}$, but the first can't be the to the second divisibility $P(p,2)$, so the second one must hold. hence we have $f(2)p^{p-1}\mid (p-1)2^{2p-1}f(p)$ which gives us $p^{p-1} \mid f(p)$ which proves the claim for all $p \neq 2$, but since we have now after cancelling out $p^{p-1}$ from both sides that $f(2) \mid (p-1)(2^{2p-1})$ for any prime $p$, we necessarely need $f(2) = 2$ Now by induction suppose $f(p^a) = p^{p^a-1}$, from $P(p, p^a)$ and noting that for any prime divisor of $f(p^{a+1}$ we need that prime divisor have multiplicity of at least $p-1$, we can conclude that any prime divisor of $f(p^{a+1})$ must divide $p$, hence $f(p^a) = p^{p^a-1}$ for all primes $p$ now we show that $(p,n) = 1 \Rightarrow (p,f(n)) = 1$ indeed, suppose $(p,n) = 1$ and $p \mid f(n)$ let $q$ be the smallest prime divisor of $n$, consider $P(q, \frac nq)$, which gives us $p \mid (q-1)(\frac nq)^{n-1}q^{q-1}$ from which we conclude $p \mid q-1$ but since we also have $p \mid f(n)$ together with $d(f(n)) = n$ we have that at least $p^{\nu_q (n)} \mid f(n)$ hence $p^{\nu_1 (n)} \mid q-1$ which is absurd Now we wish to show that $f$ is multiplicative, since that would solve the problem Indeed, consider $P(p,q)$ for two distinct primes $p,q$, it has either form $q^{pq-1}$ or $r_1^{p-1}r_2^{q-1}$, by considering both $P(p,q)$ and $P(q,p)$ we can rule out the first possibility, if now $p>q$ we have $r_1^{p-1} \mid (q-1)p^{pq-1}q^{q-1}$ from which follows $r_1 = p$, this gives us now that $r_2 = q$ now we show the general case: write $n=p^k s$ where $p$ and $s$ are coprime and suppose we have shown $f$ is multiplicative on $s$. Additionally suppose $p$ is smaller than all the primes dividing $s$. we then get from $P(p^k, s)$ that $f(n) \mid (p^k-1)s^{n-1}p^{p^k-1}$ if now $p \mid f(n)$ we have can bound the amount $p$ divides $f(n)$ by $p^k-1$ Since $p$ is the smallest prime that divides $n$, with $d(f(n)) = n$ we get that any other prime cannot replace a divisor of $p$, so $p^{p^k-1}$ fully divides into $f(n)$ which proves our claim But now for any integer $n$, we can decompose it into prime powers and then add those in decreasing order and in that way build our integer as wanted, so this proves our claim and we have as only valid solution: $$f(p_1^{\alpha_1}\dots p_k^{\alpha_k}) = \prod_{i=1}^k \left( p_i^{p_i^{\alpha_i}-1} \right)$$