Problem

Source: Indonesia IMO 2007 TST, Stage 2, Test 4, Problem 3

Tags: function, algebra, polynomial, induction, number theory proposed, number theory



Find all pairs of function $ f: \mathbb{N} \rightarrow \mathbb{N}$ and polynomial with integer coefficients $ p$ such that: (i) $ p(mn) = p(m)p(n)$ for all positive integers $ m,n > 1$ with $ \gcd(m,n) = 1$, and (ii) $ \sum_{d|n}f(d) = p(n)$ for all positive integers $ n$.