Problem 3

For any positive integer

n

, let

d(n)

denote the number of positive divisors of

n

(including

1

and

n

itself). Determine all positive integers

k

such that

\frac{d(n^2)}{d(n)}=k

for some

n

Step 2 of 6: Prove necessity

Previous step Next step

In plain words

A divisor of an odd number is odd.

d(n^2)\text{ is odd}\Rightarrow k\text{ is odd}

Detailed analysis

Because $n^2$ is a perfect square, every exponent in its factorization is even and $d(n^2)$ is odd. Since $k=d(n^2)/d(n)$ is an integer, $k$ divides the odd integer $d(n^2)$ ; therefore $k$ must be odd.