Raja Oktovin wrote: 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$. $ P(2n)=P(2)P(n)$ $ \forall$ odd $ n>1$ and so $ P(2x)=aP(x)$ $ \forall x$ (else non zero polynomial $ P(2x)-P(2)P(x)$ would have infinitely many roots). As a consequence, we get $ P(x)=0$ or $ P(x)=x^k$ for some $ k$ but, since $ f(d)>0$ ($ 0\notin\mathbb N$), we get only $ P(x)=x^k$ for some $ k$ Using then the second formula for $ n=1$, we get $ f(1)=1$ Using then the second formula for $ n=p$ prime, we get $ f(1)+f(p)=p^k$ and so $ f(p)=p^k-1$ Using then the second formula for $ n=p^2$ with $ p$ prime, we get $ f(1)+f(p)+f(p^2)=p^{2k}$ and so $ f(p^2)=p^{2k}-p^k$ An immediate induction gives $ f(p^n)=p^{nk}-p^{(n-1)k}$ for any prime $ p$ and positive integer $ n$. Using then the second formula for $ n=pq$ with $ p,q$ prime, we get $ f(1)+f(p)+f(q)+f(pq)=(pq)^k$ and so $ f(pq)=p^kq^k-p^k-q^k+1$ and so $ f(pq)=(p^k-1)(q^k-1)$ And so, with many successive inductions, it's rather easy to show that $ f(\prod p_i^{n_i})=\prod(p_i^{n_ik}-p_i^{(n_i-1)k})$ Hence the result : $ P(x)=x^k$ and $ f(\prod p_i^{n_i})=\prod(p_i^{n_ik}-p_i^{(n_i-1)k})$