7
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The proof looks alright to me. $\endgroup$ – EuYu Apr 3 '13 at 3:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Math Gems Apr 3 '13 at 4:13
  • 2
    $\begingroup$ Dear user, This proof is very elegant actually! Regards, $\endgroup$ – Matt E Apr 3 '13 at 4:29
4
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.