How to prove that every number, such that its square root is an integer, has odd number of divisors? Is it the same as saying that every number that has an odd number of divisors is a perfect square?

  • $\begingroup$ It is not equivalent to say "every number with odd number of divisors is a perfect square". $\endgroup$ – Eoin Jan 12 '15 at 0:01
  • $\begingroup$ @Eoin I think that can also be proved. Any counter examples? $\endgroup$ – KittyL Jan 12 '15 at 0:04
  • 2
    $\begingroup$ @KittyL I don't claim that it cannot be proved. Only that it is not logically equivalent. $\endgroup$ – Eoin Jan 12 '15 at 0:05

Hint $\ $ Show that the cofactor map $\ a\mapsto n/a\,$ pairs each factor of $n$ with its cofactor, giving an even number of factors, except if there is some $\, a = n/a,\,$ i.e. when $\, n = a^2$ is a perfect square.

Remark $\ $ This is a prototypical example of exploitation of involution (reflection) symmetry.

| cite | improve this answer | |
  • 1
    $\begingroup$ I'm glad I saw this, it's much better. $\endgroup$ – Eoin Jan 12 '15 at 0:27
  • $\begingroup$ It's certainly more direct, but the general formula for the number of divisors is a good thing to know. $\endgroup$ – Jorge Fernández Hidalgo Jan 12 '15 at 1:59

Let $n$ be an integer such that $n^{1/2}$ is an integer. Let $n=p_1^{k_1}\cdots p_s^{k_s}$ be the canonical prime factorization of $n$. Since $n^{1/2}$ is an integer, we have $n^{1/2}=(p_1^{k_1}\cdots p_s^{k_s})^{1/2}=p_1^{k_1/2}\cdots p_s^{k_s/2}$ and $2|k_i$ for all $i\in \{1,\dots, s\}$.

By the $\tau$ function we have $\tau(n)=\prod_{i=1}^s(k_i+1)$. Since $2|k_i$ we have that each factor of this product is odd. Thus, the product is odd and there are an odd number of divisors.

| cite | improve this answer | |
  • $\begingroup$ why must an odd product imply an odd number of divisors? $\endgroup$ – AlanH Mar 27 '16 at 19:41

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.