Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Greg Martin Aug 22 at 20:46

2 Answers 2

up vote 9 down vote accepted

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$?

share|improve this answer
    
Yeah that's basically what I said, just more briefly, IMO. –  underdog Aug 22 at 16:52
2  
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) –  Nick Aug 22 at 16:54

If $a$ amd $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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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