Proving that d(n) is odd if and only if n is a perfect square

3.3k Views Asked by At

Here is the question (and answer) in its entirety.

enter image description here

I have been tackling this for a little and I just can't seem to understand the solution whatsoever. I don't need to know how to prove it I need to understand the way they found a solution. Apparently there is some symmetry that one can always pair a divisor d(n) with n / d. But with n= 28, d(n) = 6 and 28/6 = 4.667 so you can't pair 28 with 4.6667 because it isn't a divisor. Maybe I am not understanding something. Nothing is "clear" about the symmetry for me.

2

There are 2 best solutions below

0
On BEST ANSWER

What the proof says is the the divisors of $n$ come in pairs: if $D$ divides $n$, then $\frac nD$ also divides $n$. This suggests that the number of divisors of $n$ is always even. But there's one exception: if $n=k^2$ and if we apply this argument to $k$, we obtain $k$ once again. So, in this case the number of divisors os odd.

0
On

Here is another proof.

If the prime factorization of $n$ is $$ n=\prod_ip_i^{e_i} $$ then $$ \operatorname{d}(n)=\prod_i(e_i+1) $$ $\operatorname{d}(n)$ is odd if and only if $(e_i+1)$ is odd for all $i$; that is, when $e_i$ is even for all $i$. In that case, $$ n=\left(\prod_ip_i^{e_i/2}\right)^2 $$ That is, all the $e_i$ are even if and only if $n$ is a perfect square.