Determine all positive integers $k$ such that \[\frac{d(n^{2})}{d(n)}= k\] for some $n \in \mathbb{N}$.
Problem
Source:
Tags: Divisor Functions
30.08.2007 17:46
Let $ n=\prod p_{i}^{a_{i}}$, so $ d(n)=\prod (a_{i}+1)$ and $ d(n^{2})=\prod (2a_{i}+1)$. To have $ d(n^{2})=kd(n)$, obviously $ k$ must be odd. We will prove that for any odd $ k$ it works. Obviously $ k=1$ works, so let $ w$ be the smallest odd positive integer for which it doesn't, and write $ w=2^{m}k-1$, with $ k<w$ an odd positive integer. So, $ k=\frac{d(n_{0}^{2})}{d(n_{0})}=\frac{\prod (2a_{i}+1)}{\prod (a_{i}+1)}$. Defining $ b_{i}=2^{i}((2^{m}-1)k-1)$, we get $ \frac{\prod (2b_{i}+1)}{\prod (b_{i}+1)}=\frac{2^{m}k-1}{k}$, so $ \frac{2^{m}k-1}{k}=\frac{d(n_{1}^{2})}{d(n_{1})}$. We can pick $ n_{1}$ such that $ \gcd(n_{0},n_{1})=1$ (since we're just constructing 'an' $ n_{1}$), thus $ \frac{d((n_{0}n_{1})^{2})}{d(n_{0}n_{1})}=\frac{d(n_{0}^{2})}{d(n_{0})}\frac{d(n_{1}^{2})}{d(n_{1})}=2^{m}k-1=w$ and we have constructed a valid $ n$ for $ w$, contradiction. So it is true for all odd positive integers.