Post Number:**#2** by **Thanic Nur Samin** » Wed Feb 01, 2017 6:49 pm

Beautiful problem!!!

Lemma 1: $f(2)=2, f(3)=3^2$.

Proof: $d(f(2))=2$, so $f(2)=p$ where $p$ is a prime. Also, $d(f(3))=3$, so $f(3)=q^2$ where $q$ is a prime.

Now, $f(6)=f(2\times 3)|3^5p$

$f(6)=f(3\times 2)|2\times 2^5\times q^2$.

So, the prime divisors of $f(6)$ belong to the set $\{3,p\}$ and also to the set $\{2,q\}$. This implies $p=2$ and $q=3$, from which the lemma follows.

Lemma 2: If $p$ is a prime, then $f(p)=p^{p-1}$.

Proof: If $p=2$, then by lemma 1 we are done. So we can assume that $p$ is an odd prime.

$d(f(p))=p$, and since $d$ is a multiplicative function, we get that $f(p)=q^{p-1}$.

Now, $f(2p)|p^{2p-1}\times 2$ and $f(2p)|(p-1)2^{2p-1}q^{p-1}$

So, prime divisors of $f(2p)$ belong to the sets $\{2,p\}$ and the set of prime numbers that divide $p-1$ and $2$ and $q$. So since $p$ can't be equal to $2$ and neither can it divide $p-1$. So $p=q$ and the lemma follows.

Lemma 3: If $p$ is a prime and $k$ is a positive integer, then $f(p^k)=p^{p^k-1}$

Proof: We prove by induction on $k$. For $k=1$ this follows from lemma 2.

Now, lets assume that its true for $k-1$. Now, if a prime $q$ not equal to $p$ divides $f(p^k)$, then,

$d(f(p^k))=p^k$, so $v_q(f(p^k))\ge p-1$.

$q^{p-1}|f(p^k)=f(p\times p^{k-1})|(p-1)p^s\times p^t$ for some $s$ and $t$. So we get that $q^{p-1}|p-1$. Clearly impossible for size reasons. So $f(p^k)=p^n$, and from $d(f(p^k))=p^k$ the lemma easily follows by induction.

Lemma 4: For a prime $q$, $q|f(N)\Rightarrow q|N$.

Proof: Let the smallest prime divisor of $N$ be $p$, and $q$ is a prime factor of $f(N)$. Let $e$ be the largest number such that $q^e|f(N)$

Since $d(f(N))=N$, none of the powers of prime divisors of $f(N)$ can be less than $p-1$. So $e\ge p-1$.

Again, $f(N)|(p-1)(\dfrac{N}{p})^{N-1}f(p)$ implies that $q|N$.

Now we prove the main part, that is $\displaystyle f(\prod_{i=1}^k p_i^{a_i})=\prod_{i=1}^k (p_i^{p_i^{a_i}-1})$, Where all $p_i$'s are primes. Let $\displaystyle N=\prod_{i=1}^k p_i^{a_i}$. WLOG $p_1<p_2\ldots <p_k$.

We know that $f(N)$ has the same set of prime factors of $N$. So we can write $\displaystyle f(N)=\prod_{i=1}^k p_i^{b_i}$. However, $\displaystyle \prod_{i=1}^k (b_i+1)=\prod_{i=1}^k p_i^{a_i}$.

Also, $f(N)|(p_i^{a_i}-1)(N/p_i^{a_i})^{N-1}p_i^{p^{a_i}-1}$, and so the power of $p_i$ in the prime factorization of $f(N)$ would be at most $p_i^{a_i}-1$, and from $\displaystyle \prod_{i=1}^k (b_i+1)=\prod_{i=1}^k p_i^{a_i}$ we get that the equality case must occur. So we have proved that the function can't be anything but $\displaystyle f(\prod_{i=1}^k p_i^{a_i})=\prod_{i=1}^k (p_i^{p_i^{a_i}-1})$, and testing yields that it works, so we are done.

Hammer with tact.

Because destroying everything mindlessly isn't cool enough.