$m$ is a perfect square iff $m$ has an odd number of divisors?

Solution 1:

Let $\tau(n)$ be the number of divisors of $n$.

We know that $\tau$ is multiplicative (that is, $\tau(nm)=\tau(n)\tau(m)$ when $(m,n)=1$) since $\tau(mn)=\sum_{d|mn}1=(\sum_{d|m}1)(\sum_{b|n}1)=\tau(m)\tau(n)$ whenever $m$ and $n$ are relatively prime.

For an arbitrary prime, we have $\tau(p^e)$ counting the prime powers of $p$ less than or equal to $e$. That is, the divisors of $p^e$ are $1,p,...,p^e$ of which there are clearly $e+1$.

Since we know $\tau$ is multaplicitive we can say for any $n$ that $\tau(n)=\tau(p_1^{e_1})\tau(p_2^{e_2})...\tau(p_k^{e_k})$ where $n=p_1^{e_1}...p_k^{e_k}$ is the prime factorization of $n$. From our formula above, we have $\tau(n)=(e_1+1)(e_2+1)...(e_k+1)$. So $\tau(n)$ is odd if and only if $(e_i+1)$ is odd for all $i$. This holds if and only if $e_i$ is even i.e., $e_i=2a_i$ for all $i$. Then clearly $n=p_1^{2a_1}...p_k^{e2a_k}=(p_1^{a_1}...p_k^{a_k})^2$ is a perfect square.