Suggestion: put this in the divisor function section, perhaps. This is not much like a functional equation. The answer: Let $ P\subseteq\mathbb{N}$ be the set of primes. Let $ g : P\rightarrow P$ be any bijection (i.e. it is a permutation of the primes). Then if $ n = p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$, $ f(n) = g(p_{1})^{e_{1}}g(p_{2})^{e_{2}}\cdots g(p_{k})^{e_{k}}$. The solution: Important observation: $ \tau(n) = f(\tau(n))$, since $ f$ is surjective. First, since $ \tau(n) = 1$ has only $ n = 1$ as a solution, $ f(1) = 1$. Consider any prime $ p$. Note that $ f(p)$ has only two divisors, so it's also prime. We have $ f(1)\mid f(p)$ and $ f(p)\mid f(p)$, but no other restrictions. Define $ g$ as above (permutation of primes), so that we get $ f(p) = g(p)$ for all primes $ p$. To show $ g$ must be bijective, it's sufficient to show $ f$ is bijective. We already know it's surjective. If $ f(a) = f(b)$, then $ f(a)\mid f(b)$ and $ f(b)\mid f(a)$, so $ a = b$, therefore $ f$ is also injective. Done. Now we prove by strong induction $ f(p^{k}) = g(p)^{k}$ for all positive integers $ k$. Base case $ k = 1$ just done. Suppose it's true for all numbers $ k-1$. Now $ f(p^{k})$ is divisible by $ 1, g(p),\ldots g(p)^{k-1}$, and itself, but nothing else. So $ f(p^{k})$ has $ g(p)^{k-1}$ at least in its prime factorization, and $ \tau(f(p^{k})) =\tau(p^{k}) = k+1$. Now, if $ k > 1$, then having any other primes other than $ g(p)$ in the prime factorization of $ f(p^{k})$ means that $ \tau(f(p^{k}))\geq 2k > k+1$, contradiction. So $ f(p^{k})$ is a power of $ g(p)$, and since $ f(p^{k})$ has $ k+1$ divisors, it must be $ g(p)^{k}$. Suppose $ n$ is any positive integer and $ p$ is a prime that does not divide $ n$. We now prove that $ f(n)f(p^{k}) = f(np^{k})$ for all positive integers $ k$. Since $ (n,p^{k}) = 1$, we have $ \tau(n)\tau(p^{k}) =\tau(n p^{k})$. We know $ g(p)^{k}\mid f(np^{k})$ and that $ g(p)\nmid f(n)$. So since all divisors of $ f(n)$ divide $ f(np^{k})$, and $ g(p)^{k}$ divides $ f(np^{k})$ also, we have all divisors of $ f(n)$ and $ g(p)^{k}$ in $ f(n p^{k})$. But $ \tau(f(n)g(p)^{k}) =\tau(np^{k}) =\tau(f(np^{k}))$. If $ f(np^{k})$ has any other divisors other than those in $ f(n)$ and $ g(p)^{k}$, we get $ \tau(f(np^{k})) >\tau(f(n)g(p)^{k})$ contradicting our previous statement. So $ f(np^{k})$ has its only divisors as exactly the ones in $ f(n)$ and $ g(p)^{k}$, and so by unique factorization $ f(np^{k}) = f(n)g(p)^{k}= f(n)f(p^{k})$. Since we have $ f$ for all prime powers, the claim we just proved is sufficient to define $ f$ for all natural numbers, leading to the answer given above.

MellowMelon wrote: Let $ g : P\rightarrow P$ be any bijection (i.e. it is a permutation of the primes). Perfect solution. Just a remark though: I think that with permutation, one usually denotes a bijection in which only finitely many elements are changed. So theoretically, it's not necessarily a permutation, we really can have any bijection here.

MellowMelon wrote: Important observation: $ \tau(n) = f(\tau(n))$, since $ f$ is surjective. First, since $ \tau(n) = 1$ has only $ n = 1$ as a solution, $ f(1) = 1$. Should it not be $ \tau(n) = \tau(f(n))$?

gave this task on training camp for IMO 1999.

ith_power wrote: MellowMelon wrote: Important observation: $ \tau(n) = f(\tau(n))$, since $ f$ is surjective. First, since $ \tau(n) = 1$ has only $ n = 1$ as a solution, $ f(1) = 1$. Should it not be $ \tau(n) = \tau(f(n))$? It should be.