10
$\begingroup$

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it.

For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ has odd # of positive divisors.
Thought to use induction but the perfect squares don't increase by 1.

$\Rightarrow$: If $n$ is a perfect square it must consist of 1+ prime factors each to an even power. If $n$ consists of 1+ prime factors each to an even power it must have an odd # of positive divisors.

$\Leftarrow$: If $n$ has an odd number of positive divisors it must consist of 1+ prime factors each to an even power. If $n$ consists of 1+ prime factors each to an even power it must be a perfect square.

Thanks.

$\endgroup$
  • $\begingroup$ Your first implication is good, although you should say why (all prime factors have an even power) implies (odd number of positive divisors). Your second implication, in particular the first sentence, is very much not obvious and needs explanation. $\endgroup$ – Greg Martin Aug 22 '14 at 20:46
23
$\begingroup$

HINT: Write $n = p_1^{a_1} \dots p_k^{a_k}$, where $p_1, \dots, p_k$ are distinct primes. Then the number of positive divisors of $n$ is given by $(a_1 +1)(a_2 + 1)\dots(a_k+1)$. In order for this number to be odd, each of the terms $a_i + 1$ must also be odd. What does this tell us about each $a_i$?

$\endgroup$
  • 1
    $\begingroup$ Yeah that's basically what I said, just more briefly, IMO. $\endgroup$ – miniparser Aug 22 '14 at 16:52
  • 2
    $\begingroup$ You've argued in one direction ($n$ a perfect square implies the number of positive divisors is odd), but you can use this hint to argue in the other direction (number of positive divisors is odd implies $n$ is a perfect square) $\endgroup$ – Nick Aug 22 '14 at 16:54
13
$\begingroup$

If $a$ and $b$ are distinct positive integers such that $ab=n$, call the pair $\{a,b\}$ a couple, or in the business-oriented language of today, partners. Call a positive divisor $a$ of $n$ self-sufficient if $a$ does not have a partner. Note that $a$ is self-sufficient if and only if $\frac{n}{a}=a$, that is, if and only if $n$ is a perfect square and $a$ is its square root.

If $n$ is not a perfect square, the set of positive divisors of $n$ is made up of a number, possibly $0$, of couples, so the number of divisors of $n$ is even.

If $n$ is a perfect square, then the set of of positive divisors of $n$ is made up of a number of couples, together with a self-sufficient number, so the number of positive divisors is odd.

$\endgroup$
0
$\begingroup$

If two integers multiply to equal N, you will add two divisors to your total for that number. This will be true for all values except when the two integers are the same. Divisors will always be added in pairs except in this case. So the only way to get to an odd total, is when the two divisors are equal, or N is a perfect square.

$\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.