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

Is this proof that $m$ is a perfect square iff $m$ has an odd number of divisors correct?

$\Rightarrow)$ If $m$ is a perfect square there is an $x$ such that $x = m/x$. The rest of the divisors come in pairs $d, m/d$, so $m$ has an odd number of divisors.

$\Leftarrow)$ Again, divisors come in pairs $m, m/d$ If there are an odd number of divisors, then necessarily $m/d = d$ for some divisor $d$, so $m$ is a square.

• The proof looks alright to me. – EuYu Apr 3 '13 at 3:09
• To be rigorous, I would prove that the map $\rm\:s(x) = m/x\:$ on the divisors is an involution, i.e. $\rm\:s^2(x) = x,\:$ so, having order $2$, the cycles (orbits) of this permutation are of length $2$ or $1$, so the cycle decomposition partitions the divisors into pairs and singletons (fixed points). Alternatively, one could give a direct elementary proof of said parition, avoiding any use of group theory. – Math Gems Apr 3 '13 at 4:13
• Dear user, This proof is very elegant actually! Regards, – Matt E Apr 3 '13 at 4:29

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.

• Nice answer. Thanks. – user70717 Apr 3 '13 at 3:19
• @user70717 This is the answer to a homework problem I have to turn in tomorrow. I hope you're not in my class... – user47805 Apr 3 '13 at 3:22
• I'm not sure whether I am in your class (maybe), but don't understand why you hope I'm not in it. – user70717 Apr 3 '13 at 3:29
• I don't recall having been assigned that congruence problem you asked on here, so I'm probably not. – user70717 Apr 3 '13 at 3:59

Let say $m=p_1^{x_1} p_2^{x_2}\dots p_n^{x_n}$ (every number can be expressed in that form) where $p_1,p_2,\dots ,p_n$ are prime numbers.

Now for m to be a perfect square, all $x_1,x_2,\dots ,x_n$ must be even numbers.

And now we can find number of divisors of m , and that is equal to $N(m)=(x_1+1)(x_2+1)\dots(x_2+1)$

$N(m)$ is multiplication of odd number $\therefore$ it's value is also odd.